시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 708 246 127 36.599%

문제

평면상에 n개의 점 (P1, .... ,  Pn) 이 놓여져있다고 했을 때, 거리가 최소인 두 개의 점을 구하고 그 거리를 알고 싶다.

입력

입력은 첫번째 줄에 정수로 된 점의 갯수 n이 주어진다.

두번째 줄부터 n+1번째 줄까지 2개의 정수 x,y가 공백을 사이에 두고 주어진다. 

i+1번째 줄은 Pi 의 x,y 좌표를 의미하고 n개의 점에 대해서 주어지게 된다.

점의 갯수는 2 ≦ n ≦ 500000 , 좌표의 범위는 -10000 ≦ x,y ≦10000로 주어진다.

또한, 모든 점의 좌표는 같은 것이 없이 다른 것으로 한다.

출력

가장 가까운 두 점 사이의 거리의 제곱을 출력하시오.

예제 입력 1

3
5 5
0 0
-3 -4

예제 출력 1

25

예제 입력 2

2
0 0
1 1

예제 출력 2

2
W3sicHJvYmxlbV9pZCI6IjU2MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YjQ1MCBcdWM4MTBcdWM3NTggXHVhYzcwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzYzlcdWJhNzRcdWMwYzFcdWM1ZDAgblx1YWMxY1x1Yzc1OCBcdWM4MTAgKFAxLCAuLi4uICwgJm5ic3A7UG4pIFx1Yzc3NCBcdWIxOTNcdWM1ZWNcdWM4MzhcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVhYzcwXHViOWFjXHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1Yzc3OCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxMFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWFjZTAgXHVhZGY4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjMmY2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4XHViODVjIFx1YjQxYyZuYnNwO1x1YzgxMFx1Yzc1OCBcdWFjMmZcdWMyMTgmbmJzcDtuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBuKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIDJcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IHgseVx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+aSsxXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCZuYnNwO1BpIFx1Yzc1OCZuYnNwO3gseSBcdWM4OGNcdWQ0NWNcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHVhY2UwJm5ic3A7blx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxMFx1Yzc1OCBcdWFjMmZcdWMyMThcdWIyOTQmbmJzcDsyJm5ic3A7XHUyMjY2Jm5ic3A7biZuYnNwO1x1MjI2NiZuYnNwOzUwMDAwMCAsIFx1Yzg4Y1x1ZDQ1Y1x1Yzc1OCBcdWJjOTRcdWM3MDRcdWIyOTQmbmJzcDstMTAwMDAmbmJzcDtcdTIyNjYmbmJzcDt4LHkgXHUyMjY2MTAwMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI2MTBcdWQ1NWMsJm5ic3A7XHViYWE4XHViNGUwIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YWM4M1x1Yzc3NCBcdWM1YzZcdWM3NzQmbmJzcDtcdWIyZTRcdWI5NzggXHVhYzgzXHVjNzNjXHViODVjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YjQ1MCBcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWM4MWNcdWFjZjFcdWM3NDQmbmJzcDtcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTYyMCIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHViNDUwIFx1YzgxMCIsImRlc2NyaXB0aW9uIjoiPHA+XHU1ZTczXHU5NzYyXHU0ZTBhXHUzMDZlIG4gXHU1MDBiXHUzMDZlXHU3MGI5IFAxLCAuLi4sIFBuIFx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1Zlx1MzA2OFx1MzA0ZFx1ZmYwYyBcdThkZGRcdTk2ZTJcdTMwNGNcdTY3MDBcdTVjMGZcdTMwNmVcdWZmMTJcdTcwYjlcdTMwOTJcdTZjNDJcdTMwODFcdTMwNWZcdTMwNDRcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NTE2NVx1NTI5Ylx1MzBkNVx1MzBhMVx1MzBhNFx1MzBlYlx1MzA2ZVx1ZmYxMVx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1NjU3NFx1NjU3MCBuIFx1MzA0Y1x1NjZmOFx1MzA0NFx1MzA2Nlx1MzA0Mlx1MzA4Ylx1ZmYwZSBcdWZmMTJcdTg4NGNcdTc2ZWVcdTMwNGJcdTMwODkgbisxIFx1ODg0Y1x1NzZlZVx1MzA2ZVx1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4Y1x1MzA2Ylx1MzA2Zlx1ZmYwYyBcdWZmMTJcdTMwNjRcdTMwNmVcdTZiNjNcdTY1NzRcdTY1NzAgeCwgeSBcdTMwNGNcdWZmMTFcdTMwNjRcdTMwNmVcdTUzNGFcdTg5ZDJcdTdhN2FcdTc2N2RcdTY1ODdcdTViNTdcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNDRcdTMwNjZcdTMwNDJcdTMwOGJcdWZmMGUgaSsxIFx1ODg0Y1x1NzZlZVx1MzA2ZSB4LCB5IFx1MzA2Zlx1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4YyBQaSBcdTMwNmUgeCBcdTVlYTdcdTZhMTlcdWZmMGMgUGkgXHUzMDZlIHkgXHU1ZWE3XHU2YTE5XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlIFx1MzA1M1x1MzA4Y1x1MzA4OSBuIFx1NzBiOVx1MzA2ZVx1NGUyZFx1MzA0Ylx1MzA4OVx1NjcwMFx1MzA4Mlx1OGZkMVx1MzA0NFx1ZmYxMlx1NzBiOVx1MzA5Mlx1OTA3OFx1MzA5M1x1MzA2MFx1MzA2OFx1MzA0ZFx1ZmYwYyBcdTMwNTNcdTMwNmVcdWZmMTJcdTcwYjlcdTk1OTNcdTMwNmVcdThkZGRcdTk2ZTJcdTMwNmVcdWZmMTJcdTRlNTdcdTMwOTJcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHUzMDVmXHUzMDYwXHUzMDU3XHVmZjBjIDJcdTIyNjZuXHUyMjY2MTA8c3VwPjg8XC9zdXA+IFx1MzA0Ylx1MzA2NCAtMTAwMDBcdTIyNjZ4XHUyMjY2MTAwMDAsIC0xMDAwMFx1MjI2NnlcdTIyNjYxMDAwMCBcdTMwNjhcdTMwNTdcdWZmMGMgXHVmZjE1XHUzMDY0XHUzMDZlXHU1MTY1XHU1MjliXHUzMGQ1XHUzMGExXHUzMGE0XHUzMGViXHUzMDZlXHUzMDQ2XHUzMDYxXHVmZjEzXHUzMDY0XHUzMDY3XHUzMDZmIG5cdTIyNjYxMDAgXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlIFx1MzA3ZVx1MzA1Zlx1ZmYwY1x1MzA2OVx1MzA2ZVx1NTE2NVx1NTI5Ylx1MzBkNVx1MzBhMVx1MzBhNFx1MzBlYlx1MzA2Ylx1MzA0YVx1MzA0NFx1MzA2Nlx1MzA4Mlx1ZmYwY1x1NTE2OFx1MzA2Nlx1MzA2ZVx1NWVhN1x1NmExOVx1MzA2Zlx1NzU3MFx1MzA2YVx1MzA4Ylx1MzA4Mlx1MzA2ZVx1MzA2OFx1MzA1OVx1MzA4Ylx1ZmYwZTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1NTE2NVx1NTI5Ylx1MzBkNVx1MzBhMVx1MzBhNFx1MzBlYlx1MzA2ZVx1NjUzOVx1ODg0Y1x1MzBiM1x1MzBmY1x1MzBjOVx1MzA2ZiBDUitMRiBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGUgXHUzMDdlXHUzMDVmXHVmZjBjIFx1NTFmYVx1NTI5Ylx1MzBkNVx1MzBhMVx1MzBhNFx1MzBlYlx1MzA2Ylx1MzA0YVx1MzA0NFx1MzA2Nlx1MzA2Zlx1ZmYwYyBcdTUxZmFcdTUyOWJcdTMwNmVcdTY3MDBcdTVmOGNcdTMwNmVcdTg4NGNcdTMwNmJcdTMwODJcdTY1MzlcdTg4NGNcdTMwYjNcdTMwZmNcdTMwYzlcdTMwOTJcdTUxNjVcdTMwOGNcdTMwOGJcdTMwNTNcdTMwNjhcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM3N2NcdWJjZjhcdWM1YjQifV0=