시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB3205104063642.485%

문제

평면상에 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+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHViNDUwIFx1YzgxMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHVjNzU4IFx1YzgxY1x1YWNmMVx1Yzc0NCZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1NjIwIiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHU1NTRmXHU5ODRjIDQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1NWU3M1x1OTc2Mlx1NGUwYVx1MzA2ZSBuIFx1NTAwYlx1MzA2ZVx1NzBiOSBQMSwgLi4uLCBQbiBcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTMwNjhcdTMwNGRcdWZmMGMgXHU4ZGRkXHU5NmUyXHUzMDRjXHU2NzAwXHU1YzBmXHUzMDZlXHVmZjEyXHU3MGI5XHUzMDkyXHU2YzQyXHUzMDgxXHUzMDVmXHUzMDQ0XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTUxNjVcdTUyOWJcdTMwZDVcdTMwYTFcdTMwYTRcdTMwZWJcdTMwNmVcdWZmMTFcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdTY1NzRcdTY1NzAgbiBcdTMwNGNcdTY2ZjhcdTMwNDRcdTMwNjZcdTMwNDJcdTMwOGJcdWZmMGUgXHVmZjEyXHU4ODRjXHU3NmVlXHUzMDRiXHUzMDg5IG4rMSBcdTg4NGNcdTc2ZWVcdTMwNmVcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTMwNmJcdTMwNmZcdWZmMGMgXHVmZjEyXHUzMDY0XHUzMDZlXHU2YjYzXHU2NTc0XHU2NTcwIHgsIHkgXHUzMDRjXHVmZjExXHUzMDY0XHUzMDZlXHU1MzRhXHU4OWQyXHU3YTdhXHU3NjdkXHU2NTg3XHU1YjU3XHUzMDkyXHU1MzNhXHU1MjA3XHUzMDhhXHUzMDY4XHUzMDU3XHUzMDY2XHU2NmY4XHUzMDQ0XHUzMDY2XHUzMDQyXHUzMDhiXHVmZjBlIGkrMSBcdTg4NGNcdTc2ZWVcdTMwNmUgeCwgeSBcdTMwNmZcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGMgUGkgXHUzMDZlIHggXHU1ZWE3XHU2YTE5XHVmZjBjIFBpIFx1MzA2ZSB5IFx1NWVhN1x1NmExOVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZSBcdTMwNTNcdTMwOGNcdTMwODkgbiBcdTcwYjlcdTMwNmVcdTRlMmRcdTMwNGJcdTMwODlcdTY3MDBcdTMwODJcdThmZDFcdTMwNDRcdWZmMTJcdTcwYjlcdTMwOTJcdTkwNzhcdTMwOTNcdTMwNjBcdTMwNjhcdTMwNGRcdWZmMGMgXHUzMDUzXHUzMDZlXHVmZjEyXHU3MGI5XHU5NTkzXHUzMDZlXHU4ZGRkXHU5NmUyXHUzMDZlXHVmZjEyXHU0ZTU3XHUzMDkyXHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1MzA1Zlx1MzA2MFx1MzA1N1x1ZmYwYyAyXHUyMjY2blx1MjI2NjEwPHN1cD44PFwvc3VwPiBcdTMwNGJcdTMwNjQgLTEwMDAwXHUyMjY2eFx1MjI2NjEwMDAwLCAtMTAwMDBcdTIyNjZ5XHUyMjY2MTAwMDAgXHUzMDY4XHUzMDU3XHVmZjBjIFx1ZmYxNVx1MzA2NFx1MzA2ZVx1NTE2NVx1NTI5Ylx1MzBkNVx1MzBhMVx1MzBhNFx1MzBlYlx1MzA2ZVx1MzA0Nlx1MzA2MVx1ZmYxM1x1MzA2NFx1MzA2N1x1MzA2ZiBuXHUyMjY2MTAwIFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZSBcdTMwN2VcdTMwNWZcdWZmMGNcdTMwNjlcdTMwNmVcdTUxNjVcdTUyOWJcdTMwZDVcdTMwYTFcdTMwYTRcdTMwZWJcdTMwNmJcdTMwNGFcdTMwNDRcdTMwNjZcdTMwODJcdWZmMGNcdTUxNjhcdTMwNjZcdTMwNmVcdTVlYTdcdTZhMTlcdTMwNmZcdTc1NzBcdTMwNmFcdTMwOGJcdTMwODJcdTMwNmVcdTMwNjhcdTMwNTlcdTMwOGJcdWZmMGU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTUxNjVcdTUyOWJcdTMwZDVcdTMwYTFcdTMwYTRcdTMwZWJcdTMwNmVcdTY1MzlcdTg4NGNcdTMwYjNcdTMwZmNcdTMwYzlcdTMwNmYgQ1IrTEYgXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlIFx1MzA3ZVx1MzA1Zlx1ZmYwYyBcdTUxZmFcdTUyOWJcdTMwZDVcdTMwYTFcdTMwYTRcdTMwZWJcdTMwNmJcdTMwNGFcdTMwNDRcdTMwNjZcdTMwNmZcdWZmMGMgXHU1MWZhXHU1MjliXHUzMDZlXHU2NzAwXHU1ZjhjXHUzMDZlXHU4ODRjXHUzMDZiXHUzMDgyXHU2NTM5XHU4ODRjXHUzMGIzXHUzMGZjXHUzMGM5XHUzMDkyXHU1MTY1XHUzMDhjXHUzMDhiXHUzMDUzXHUzMDY4XHVmZjBlPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiSmFwYW5lc2UifV0=