문제 B: 최근접 점의 쌍 찾기
실행시간 제한: 1 Sec 메모리사용 제한: 128 MB제출: 274 통과: 28
[제출] [채점기록] [묻고답하기] [만든사람:]
문제 설명
아래 그림과 같이 2차원 평면상에 n개의 점이 입력으로 주어질 때, 유클리드 거리가 가장 가까운 한 쌍의 점을 찾아 그 점들의 좌표를 출력하는 프로그램을 작성하시오.
입력 설명
첫 번쨰 줄에 2차원 평면상에 존재하는 점의 갯수 n이 주어진다(3 <= n <= 20,000).
그 다음 줄부터 (i, j) 좌표가 n줄 입력된다.(-10,000 <= i, j<= 10,000)
그 다음 줄부터 (i, j) 좌표가 n줄 입력된다.(-10,000 <= i, j<= 10,000)
출력 설명
입력된 점들 중에 유클리드 거리가 가장 가까운 두 점의 좌표를 출력하되, x 좌표의 값이 작은 좌표를 먼저 출력하고, 만약 x 좌표의 값이 같을 경우에는 y 좌표값이 작은 것을 먼저 출력한다.
세부적인 출력 형식은 출력 예시를 참고하시오.
세부적인 출력 형식은 출력 예시를 참고하시오.
입력 예시 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
출력 예시 Copy
(8665, 4572) (9052, 5109)
도움
분할 정복