Problem B: 최근접 점의 쌍 찾기
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 274 Solved: 28
[Submit] [Status] [Web Board] [Creator:]
Description
아래 그림과 같이 2차원 평면상에 n개의 점이 입력으로 주어질 때, 유클리드 거리가 가장 가까운 한 쌍의 점을 찾아 그 점들의 좌표를 출력하는 프로그램을 작성하시오.
Input
첫 번쨰 줄에 2차원 평면상에 존재하는 점의 갯수 n이 주어진다(3 <= n <= 20,000).
그 다음 줄부터 (i, j) 좌표가 n줄 입력된다.(-10,000 <= i, j<= 10,000)
그 다음 줄부터 (i, j) 좌표가 n줄 입력된다.(-10,000 <= i, j<= 10,000)
Output
입력된 점들 중에 유클리드 거리가 가장 가까운 두 점의 좌표를 출력하되, x 좌표의 값이 작은 좌표를 먼저 출력하고, 만약 x 좌표의 값이 같을 경우에는 y 좌표값이 작은 것을 먼저 출력한다.
세부적인 출력 형식은 출력 예시를 참고하시오.
세부적인 출력 형식은 출력 예시를 참고하시오.
Sample Input Copy
20
1893 -552
-5607 2110
156 266
8461 -4475
5526 -8003
9052 5109
-7490 2509
-1645 8609
5543 3975
-4817 8855
2796 2914
-7001 1747
1775 -8900
-6990 6100
-2386 -3177
-5978 8417
-4201 6653
-6253 9823
-3694 5171
8665 4572
Sample Output Copy
(8665, 4572) (9052, 5109)
HINT
분할 정복