%2021. 12. 3. 10:13에 작성된 글입니다%
2261번: 가장 가까운 두 점
첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도
www.acmicpc.net
분할 정복의 대표적인 예제로 많이 쓰이는 문제인 것 같던데 스위핑으로 푸는 게 아이디어 잡기도 구현도 훨씬 나은 듯. 약간의 데이터 처리와 이분 탐색 스위핑으로 그냥 풀린다. 분할 정복으로 풀면 P2-P1일지도 모르겠는데 스위핑으로 풀면 P2-P1 수준까지는 아닌듯...
내가 스위핑으로 풀었으니까 여기에는 스위핑 풀이 적음
전반적인 흐름:
x 값이 작은 점부터 큰 점까지 쭉 돌면서 검사.
1. 우선 같은 x좌표를 가진 점들을 sort해서 for문 돌려 최소 거리 구하기 (한개면 INF)
2. 현재까지의 최소 거리보다 x 사이 거리가 짧고 왼쪽에 있는 점들만 대상으로:
2-1. x간 거리가 같은 모든 점들에 대하여
2-2. y간 거리가 가장 짧은 점을 찾고 거리 구하기 / 최솟값 갱신
이 때 1번 과정에서 sort를 때리기 때문에 2-2에서는 Binary search를 할 수 있고 그럼 시복도 많이 줄어든다.정렬에는 \(O(N\log N)\)이고 스위핑은 아마 최악의 경우라도 \(O(N)\)랑 비슷하지 않을까?
아님 말고... 여튼 TLE 안 났으니까 이 정도로 족한 건 맞는 듯.
실제 구현도 그리 까다롭진 않음. 좌표 범위 작으니까 좌표 압축 느낌으로다가...