Closest Pair

문제의 특성상 그림이 설명에 중요한 역할을 하나,

포스트에 그리기가 번거로우므로 생략하고, 노트에 있는 그림을 참고한다.

문제 정의 : 평면 상의 n개의 점들 중 가장 가까운 한 쌍을 찾아라.

- 이 문제의 입력은 그래프가 아니라 x좌표, y좌표가 주어진 점들의 집합이다.

Alg.

1. 입력을 x축 기준으로 정렬해서 반으로 나눈다.

2. 재귀적으로 호출한다.

3. (merge sort를 사용하여) y축 기준으로 정렬하며 합친다.

* 반으로 나뉠때 가운데에 잘린 것들은 어떻게 비교할 것인가? ( 하나는 왼쪽에, 다른 하나는 오른쪽에 있는 경우 )

- 왼쪽에서 찾은 제일 짧은 선과 오른쪽에서 찾은 제일 짧은 선, 둘 중에 더 짧은 선을 d라 하자.

- x축의 중심에서 왼쪽으로 d, 오른쪽으로 d만큼의 영역을 "밴드"라 하자.

- 밴드 안의 특정한 점에 대해서 y축 방향으로 d만큼 차이나는 점과의 거리만 보면 된다.

- 그리고 그 점들은 무조건 10개 이하이다.

  -> 거리가 d인 정사각형 안에 d보다 긴 거리를 가지는 점들은 최대 3개까지 밖에 넣지 못한다.

- 밴드 안에 있는 점들을 y축 기준으로 정렬해야 한다.
- 한 레벨에서 nlogn 만큼의 시간을 쓰기 때문에, 전체 알고리즘의 수행시간은 n(logn)^2 이 된다.

* 밴드 안에 있는 점들만 보면 되지만, 모든 점들을 sort하는 것이 더 좋다.

왜냐하면 밴드 안에 있는 점들만 sort하려면 각 레벨마다 "그 레벨의 밴드 안에 있는 점들"을 y축을 기준으로 새로 정렬해야 하지만,

애초에 모든 점들을 sort하겠다고 한다면, 합치면서 merge sort를 사용할 수 있기 때문이다.

또한, 모든 점을 sort 해도, 실제 스캔은 밴드 안에 있는 점만을 찾아서 계산하기 때문에
작업이 크게 늘어나지 않는다. ( 밴드 밖에 있는 점을 건너뛰는 시간이 더해질 뿐이다.)

- 합치면서 merge sort를 하게 된다면, 한 레벨에서 n만큼의 시간을 쓰게 되고,
 전체 알고리즘의 수행시간이 nlogn이 된다.

- 기존의 작업은 아래 레벨에서의 결과물이 현재 레벨에서 아무 도움이 되지 않는다.
 ( 밴드의 위치는 레벨마다 다르기 때문에 현재 레벨에서 다시 정렬을 수행해야 한다.)
 merge sort를 사용하면 아래 레벨에서의 결과물이 현재 레벨에서 도움이 된다.
 ( 양쪽 배열이 이미 정렬되어 있으므로, merge기법을 통해 간단히 합칠 수 있게 되는것.)