시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 116 18 14 27.451%

문제

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

입력

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

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

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

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

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

출력

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

예제 입력

3
5 5
0 0
-3 -4

예제 출력

25

예제 입력 2

2
0 0
1 1

예제 출력 2

2

힌트