6005 : 분할정복 — 최근접 점 쌍
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
2차원 평면 위에 $N$개의 점이 주어집니다. 이 중에서 가장 거리가 가까운 두 점 사이의 거리를 구하십시오.
분할 정복 기법을 이용하여 $O(N \log N)$ 시간 복잡도로 구현해야 합니다.
[제약 조건]
• 점의 개수 $N$: $2 \le N \le 100{,}000$ (정수)
• 좌표 $x, y$: $-10^9 \le x, y \le 10^9$ (실수)
• 결과는 소수점 넷째 자리까지 출력합니다.
분할 정복 기법을 이용하여 $O(N \log N)$ 시간 복잡도로 구현해야 합니다.
[제약 조건]
• 점의 개수 $N$: $2 \le N \le 100{,}000$ (정수)
• 좌표 $x, y$: $-10^9 \le x, y \le 10^9$ (실수)
• 결과는 소수점 넷째 자리까지 출력합니다.
입력 설명
첫째 줄에 점의 개수 $N$이 주어집니다.
둘째 줄부터 $N$개의 줄에 각 점의 $x, y$ 좌표가 공백으로 구분되어 주어집니다.
[제약 조건]
• $2 \le N \le 100{,}000$
• 좌표 $x, y$는 $-10^9$ 이상 $10^9$ 이하의 정수
출력 설명
가장 가까운 두 점 사이의 거리를 소수점 넷째 자리까지 반올림하여 출력합니다. (예: 1.4142)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
0 0
3 4
1 1
5 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1.4142도움
$x$좌표 정렬 후 분할 정복으로 좌우 최단 거리 $d$를 구하고, 중앙선 기준 거리 $d$ 이내 점들만 $y$좌표로 스위핑합니다.