시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 512 MB 307 22 (7%) 16
문제
2차원 평면상에 N개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 점의 수 N이 주어진다. (2 ≤ N ≤ 500,000) 두 번째 줄부터 N개의 줄에 걸쳐 각 점의 좌표인 x, y가 주어진다. (-10,000 ≤ x, y ≤ 10,000)
출력
첫 번째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다.
힌트
#### 예제 입력 ``` 4 0 0 10 10 0 10 10 0 ``` #### 예제 출력 ``` 100 ``` 다음 자료에 설명된 알고리즘을 이용하여 해결할 수 있다. - http://www.cs.colostate.edu/~cs320/Slides/05_clspr.pdf