시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 806 247 137 42.154%

문제

평면상에 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+XHVjNzg1XHViODI1XHVjNzQwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWI0MWMmbmJzcDtcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4Jm5ic3A7blx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIG4rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgMlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggeCx5XHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5pKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzQwJm5ic3A7UGkgXHVjNzU4Jm5ic3A7eCx5IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAmbmJzcDtuXHVhYzFjXHVjNzU4IFx1YzgxMFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCZuYnNwOzImbmJzcDtcdTIyNjYmbmJzcDtuJm5ic3A7XHUyMjY2Jm5ic3A7NTAwMDAwICwgXHVjODhjXHVkNDVjXHVjNzU4IFx1YmM5NFx1YzcwNFx1YjI5NCZuYnNwOy0xMDAwMCZuYnNwO1x1MjI2NiZuYnNwO3gseSBcdTIyNjYxMDAwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YywmbmJzcDtcdWJhYThcdWI0ZTAgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWFjMTlcdWM3NDAgXHVhYzgzXHVjNzc0IFx1YzVjNlx1Yzc3NCZuYnNwO1x1YjJlNFx1Yjk3OCBcdWFjODNcdWM3M2NcdWI4NWMgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHViNDUwIFx1YzgxMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHVjNzU4IFx1YzgxY1x1YWNmMVx1Yzc0NCZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NjIwIiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWI0NTAgXHVjODEwIiwiZGVzY3JpcHRpb24iOiI8cD5cdTVlNzNcdTk3NjJcdTRlMGFcdTMwNmUgbiBcdTUwMGJcdTMwNmVcdTcwYjkgUDEsIC4uLiwgUG4gXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHUzMDY4XHUzMDRkXHVmZjBjIFx1OGRkZFx1OTZlMlx1MzA0Y1x1NjcwMFx1NWMwZlx1MzA2ZVx1ZmYxMlx1NzBiOVx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA1Zlx1MzA0NFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMGQ1XHUzMGExXHUzMGE0XHUzMGViXHUzMDZlXHVmZjExXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIG4gXHUzMDRjXHU2NmY4XHUzMDQ0XHUzMDY2XHUzMDQyXHUzMDhiXHVmZjBlIFx1ZmYxMlx1ODg0Y1x1NzZlZVx1MzA0Ylx1MzA4OSBuKzEgXHU4ODRjXHU3NmVlXHUzMDZlXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHUzMDZiXHUzMDZmXHVmZjBjIFx1ZmYxMlx1MzA2NFx1MzA2ZVx1NmI2M1x1NjU3NFx1NjU3MCB4LCB5IFx1MzA0Y1x1ZmYxMVx1MzA2NFx1MzA2ZVx1NTM0YVx1ODlkMlx1N2E3YVx1NzY3ZFx1NjU4N1x1NWI1N1x1MzA5Mlx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2OFx1MzA1N1x1MzA2Nlx1NjZmOFx1MzA0NFx1MzA2Nlx1MzA0Mlx1MzA4Ylx1ZmYwZSBpKzEgXHU4ODRjXHU3NmVlXHUzMDZlIHgsIHkgXHUzMDZmXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjIFBpIFx1MzA2ZSB4IFx1NWVhN1x1NmExOVx1ZmYwYyBQaSBcdTMwNmUgeSBcdTVlYTdcdTZhMTlcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGUgXHUzMDUzXHUzMDhjXHUzMDg5IG4gXHU3MGI5XHUzMDZlXHU0ZTJkXHUzMDRiXHUzMDg5XHU2NzAwXHUzMDgyXHU4ZmQxXHUzMDQ0XHVmZjEyXHU3MGI5XHUzMDkyXHU5MDc4XHUzMDkzXHUzMDYwXHUzMDY4XHUzMDRkXHVmZjBjIFx1MzA1M1x1MzA2ZVx1ZmYxMlx1NzBiOVx1OTU5M1x1MzA2ZVx1OGRkZFx1OTZlMlx1MzA2ZVx1ZmYxMlx1NGU1N1x1MzA5Mlx1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGMgMlx1MjI2Nm5cdTIyNjYxMDxzdXA+ODxcL3N1cD4gXHUzMDRiXHUzMDY0IC0xMDAwMFx1MjI2NnhcdTIyNjYxMDAwMCwgLTEwMDAwXHUyMjY2eVx1MjI2NjEwMDAwIFx1MzA2OFx1MzA1N1x1ZmYwYyBcdWZmMTVcdTMwNjRcdTMwNmVcdTUxNjVcdTUyOWJcdTMwZDVcdTMwYTFcdTMwYTRcdTMwZWJcdTMwNmVcdTMwNDZcdTMwNjFcdWZmMTNcdTMwNjRcdTMwNjdcdTMwNmYgblx1MjI2NjEwMCBcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGUgXHUzMDdlXHUzMDVmXHVmZjBjXHUzMDY5XHUzMDZlXHU1MTY1XHU1MjliXHUzMGQ1XHUzMGExXHUzMGE0XHUzMGViXHUzMDZiXHUzMDRhXHUzMDQ0XHUzMDY2XHUzMDgyXHVmZjBjXHU1MTY4XHUzMDY2XHUzMDZlXHU1ZWE3XHU2YTE5XHUzMDZmXHU3NTcwXHUzMDZhXHUzMDhiXHUzMDgyXHUzMDZlXHUzMDY4XHUzMDU5XHUzMDhiXHVmZjBlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMGQ1XHUzMGExXHUzMGE0XHUzMGViXHUzMDZlXHU2NTM5XHU4ODRjXHUzMGIzXHUzMGZjXHUzMGM5XHUzMDZmIENSK0xGIFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZSBcdTMwN2VcdTMwNWZcdWZmMGMgXHU1MWZhXHU1MjliXHUzMGQ1XHUzMGExXHUzMGE0XHUzMGViXHUzMDZiXHUzMDRhXHUzMDQ0XHUzMDY2XHUzMDZmXHVmZjBjIFx1NTFmYVx1NTI5Ylx1MzA2ZVx1NjcwMFx1NWY4Y1x1MzA2ZVx1ODg0Y1x1MzA2Ylx1MzA4Mlx1NjUzOVx1ODg0Y1x1MzBiM1x1MzBmY1x1MzBjOVx1MzA5Mlx1NTE2NVx1MzA4Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1Yzc3Y1x1YmNmOFx1YzViNCJ9XQ==