가장 가까운 두 점
시간 제한1초메모리 제한256 MB
최대 10만 개의 점이 주어질 때 두 점 사이 최소 제곱거리를 효율적으로 구하는 문제입니다.
문제
2차원 평면 위에 n개의 점이 주어진다. 이 점들 중 서로 가장 가까운 두 점을 찾아, 두 점 사이 거리의 제곱을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 n (2 <= n <= 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 x좌표와 y좌표가 주어진다. 각 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 좌표를 가진 점이 여러 개 주어질 수도 있다.
출력
가장 가까운 두 점 사이 거리의 제곱을 출력한다.