[BOJ2261] 가장 가까운 두 점

1. 문제

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

2. Note

반으로 나눠서(Divide) 절반 크기의 문제 두 개를 풀고 반으로 나누는 기준 선분 근처의 쌍을 살펴보면 되겠다(Conquer)는 생각이 들었지만 Conquer 단계에서 O(n^2) 아래의 방법이 떠오르지 않아서 해결하지 못했다. (참고로 이러한 분할 정복 기법은 모든 쌍을 모든 문제에서 자주 쓰인다고 한다.)

2.1. 핵심 아이디어

Conquer 단계를 O(nlogn) 이하로 만드는 핵심 아이디어는 약간의 수학(특히 기하학)적 사고가 필요했다.
(https://math.stackexchange.com/questions/45776/closest-pair-of-points-algorithm)

2.2. vector::size()

C++ 컨테이너의 size()는 size_t를 반환하는데, 이는 unsigned의 정수형이다. 따라서 컨테이너의 크기가 0일 때 size()에서 1을 빼면 underflow가 발생하게 된다. unsigned와 signed를 섞어 쓸 때는 주의해야 한다.

2.3. vector::reserve()

reserve()는 말 그대로 공간을 예약해두는 것이다. 따라서 잘 활용하면 반복해서 공간을 재할당하고 데이터를 이동하는 것을 방지할 수 있으므로 효율적일 수 있다.

2.4. 경계 값

큰 틀의 로직은 맞았는데 경계 값 조건을 잘못 설정해서(필요 이상으로 검사함) 시간 초과를 받았었다.
(그런데 이 케이스는 좀 더 검증해 보아야 할 것 같다.)

2.5. 더 빠른 알고리즘

이번에 구현한 알고리즘은 시간복잡도가 O(n(logn)^2)인데, 아래와 같이 구현하면 시간복잡도를 더 줄일 수 있다고 한다.

• y축 기준으로 정렬할 때 병합 정렬의 아이디어를 사용하면 Conquer 단계를 O(n)으로 해결할 수 있다고 한다. => 전체 시간복잡도 O(nlogn)
• Line Sweep 기법 => O(nlogn)

3. Reference

3.1. 알고리즘

• https://blog.encrypted.gg/127
• https://casterian.net/archives/92

3.2. 핵심 아이디어 증명

• https://math.stackexchange.com/questions/45776/closest-pair-of-points-algorithm

3.3. unsigned와 signed의 연산

• https://stackoverflow.com/questions/25609091/what-happens-when-i-mix-signed-and-unsigned-types

3.4. Master Thm.

• http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf