BOJ 2261 가장 가까운 두 점

https://www.acmicpc.net/problem/2261
시간 1초, 메모리 256MB
input :

• n(2 ≤ n ≤ 100,000)
• 각 점의 x, y좌표(절댓값이 10,000을 넘지 않는 정수)
• 여러 점이 같은 좌표(set을 이용하자.)

output :

• 가장 가까운 두 점의 거리의 제곱을 출력

---

그냥 완전 탐색으론 당연히 불가능 하다. 시간복잡도가 너무 크다.

그래서 분할 정복 방법을 이용한다.

x좌표를 기준으로 정렬을 하고 중간 지점을 찾아 선을 그어 나눈다고 할 떄,
1. 두 점이 왼쪽에만 존재.
2. 두 점이 오른쪽에만 존재.
3. 두 점이 기준선을 걸쳐서 존재.

이를 시간복잡도를 줄이기 위해.
x를 기준으로 최대 거리를 찾는다.

x 좌표 기준 거리 구한 것이 최대 거리 보다 작은 것들만 temp에 모아준다.
temp에 들어온 것들을 y 기준으로 정렬한다.

그리고 y 좌표들의 거리 차이가 최대거리 보다 작은 것들을 min으로 비교해서 최대거리를 업데이트 한다.

그렇다면 return 해온 d를 이용해서 계산을 했을 때 그 안 에 존재하는 좌표가 없으면 어떻게 되나요? 현재까지 가장 짧은 거리는 d이니까 계속 d를 리턴하자.

재귀를 통해 가~~~장 짧은 거리를 구한 다음.
그것보다 큰 배열에서 중간 지점에서 이것보다 짧은 곳에 위치한 좌표각 있나??? 하면서 찾는 것이다..

정답 코드:

import sys


def dist(p, q):
    return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2


def closest_pair(start, end):
    length = end - start
    if length == 2:
        return dist(position[start], position[start + 1])
    if length == 3:
        return min(dist(position[start], position[start + 1]), dist(position[start + 1], position[start + 2]), dist(position[start], position[start + 2]))

    mid = (start + end) // 2
    # 중간에 위치하는 x좌표를 찾기 위함.
    mid_pos = position[mid][0]
    # 그 x 좌표를 기준으로 왼쪽과 오른쪽에서 최소한의 거리를 이루는 지점을 찾음
    d = min(closest_pair(start, mid), closest_pair(mid, end))

    # d 거리 안에 존재하는 점들을 걸러냄.
    temp = []
    for i in range(start, end):
        if (mid_pos - position[i][0]) ** 2 <= d:
            temp.append(position[i])

    # y 좌표를 기준으로 정렬.
    temp.sort(key=lambda x:x[1])

    temp_d = d
    temp_len = len(temp)
    for i in range(temp_len - 1):
        for j in range(i + 1, temp_len):
        	# d보다 거리가 멀다면 최단 거리가 될 수 없기 떄문에 예외처리가 필요하다.
            if (temp[i][1] - temp[j][1]) ** 2 > temp_d:
                break
            if (temp[i][1] - temp[j][1]) ** 2 < temp_d:
                d = min(d, dist(temp[i], temp[j]))
    return d


n = int(sys.stdin.readline())
pos = []
for i in range(n):
    x, y = map(int, sys.stdin.readline().split())
    pos.append((x, y))

temp_pos = set(pos)
position = list(temp_pos)

if len(pos) != len(position):
    print(0)
else:
    position.sort()
    d = closest_pair(0, len(pos))
    print(d)

참고:
https://hon6036.github.io/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5/2261/
https://casterian.net/archives/92