[BOJ] 2261번: 가장 가까운 두 점

https://www.acmicpc.net/problem/2261

모든 점을 전수조사하면 $O(N^2)$이 걸립니다. 대신에 divide and conquer로, 점들을 우선 x좌표 기준으로 정렬한 뒤, y축과 평행한 적절한 기준선으로 점을 두 그룹(그룹1, 그룹2)으로 나눕니다. 그룹1 내에서의 최소인 거리를 d1, 그룹2 내에서의 최소인 거리를 d2라고 할 때 d = min(d1, d2)라고 잡고 기준선으로부터 x축 거리가 d 이하로 떨어진 점들만 수집해 y축으로 정렬하고 나면 비둘기집의 원리에 의해 각 점에서 인접한 6개의 점만 살펴보면 됩니다.

시간복잡도는 $O(N(lgN)^2)$이 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/2261.cpp