문제

• 
• 시간 제한: 1 초
• 메모리 제한: 256 MB

Problem Analysis

주어진 점으로 만들 수 있는 모든 쌍을 하나하나 조사한다면, 시간 복잡도는 O(n^2)이다.
더 빠른 알고리즘을 생각해야 한다. 구간을 나눠서 문제를 쪼갤 수 있을 것 같다.

Algorithm

Divide and Conquer를 이용할 수 있을 것 같다.

preprocess
배열을 x좌표 기준으로 정렬한다.

1) Divide:
x좌표를 기준으로 평면을 좌우로 나눈다.

2) Conquer:
평면이 충분히 쪼개질 때까지 recursive call을 한 후, 각 부분 평면에서 최소 거리를 찾는다.

3) Combine:
결과물들을 조합하면서, 각 평면의 최소 거리 중에서 가장 작은 d를 구한다.

이때, 두 평면의 경계면에 있는 점들 간의 거리는 조사가 안 된 상태이다.
그러나, 여기를 그냥 brute force로 계산하면 O(n^2)이 걸린다.
경계면으로부터 d 미만에 있는 점들을 모아서, y축 기준으로 조사하면 된다.

Data Structure

(x, y) 좌표를 담는 struct와, 이를 담는 배열이 필요하다.

결과

Other

Conquer에서, 평면이 충분히 나누어졌을 경우, 평면을 계속 쪼개는 것보다,
brute force로 푸는 게 오히려 더 빠를 것이다.
기준은 적당히 두면 될 것인데, 평면에 점이 3개 이하가 남았을 때로 설정했다.