[BOJ] 13509번: 가장 가까운 두 점 2

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

각 점에 대해 왼쪽 아래, 왼쪽 위, 오른쪽 아래, 오른쪽 위 네 방향에서 가장 가까이 있는 점을 찾을 것입니다. 네 방향 중에 하나만 하면 나머지는 쉽게 할 수 있으니까 왼쪽 아래 방향만 생각합시다. 우선 점들의 y좌표를 좌표압축을 해둡니다. 예를 들어 (0, 0), (3, 100), (45, 26), (6, 7)일 경우 0 -> 0, 7 -> 1, 26 -> 2, 100 -> 3에 미리 대응시켜둡니다. map을 이용하면 다소 쉽게 할 수 있습니다. 이후에 x좌표 순으로 점들을 보면서 아래와 같은 작업을 합니다.

1. segment tree 상에서 0번째~(좌표압축한 y좌표)번째의 x+y의 최댓값을 찾는다.

2. 그 최댓값과 내 (x,y)의 차이가 왼쪽 아래 방향의 최단거리이다.

3. segment tree의 (좌표압축한 y좌표)번째에 x+y를 갱신시킨다.

segment tree 상에서 나보다 x+y가 작은 노드만 확인하므로 이 알고리즘의 정당성이 증명됩니다.

https://github.com/blisstoner/BOJ/blob/master/13509.cpp