7286 : 가장 가까운 점
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 2차원 점이 주어질 때, 가장 가까운 두 점 사이의 거리의 제곱을 구하십시오.
분할 정복 또는 완전 탐색으로 구현합니다. ($N \le 1{,}000$이므로 $O(N^2)$도 허용)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
분할 정복 또는 완전 탐색으로 구현합니다. ($N \le 1{,}000$이므로 $O(N^2)$도 허용)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 점의 개수 $N$이 주어집니다. ($2 \le N \le 1{,}000$)
둘째 줄부터 $N$개의 줄에 각 점의 $x$, $y$ 좌표 (정수)가 주어집니다.
둘째 줄부터 $N$개의 줄에 각 점의 $x$, $y$ 좌표 (정수)가 주어집니다.
출력 설명
가장 가까운 두 점 사이의 거리의 제곱(정수)을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
0 0
3 4
1 1
5 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
모든 쌍에 대해 $d^2 = (x_1-x_2)^2 + (y_1-y_2)^2$를 계산하고 최솟값을 구합니다. 분할 정복을 사용하면 $O(N \log N)$이지만 $N \le 1{,}000$에서는 $O(N^2)$로 충분합니다.