import sys
n = int(sys.stdin.readline())
sorted_location = []
for _ in range(n):
x, y = list(map(int, sys.stdin.readline().split()))
sorted_location.append((x, y))
sorted_location.sort()
def get_dist(a, b):
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
def solution(l, r):
if l == r:
return float('inf')
else:
m = (l + r) // 2
min_dist = min(solution(l, m), solution(m + 1, r))
target_list = []
for i in range(m, l - 1, -1):
if (sorted_location[i][0] - sorted_location[m][0]) ** 2 < min_dist:
target_list.append(sorted_location[i])
else:
break
for j in range(m + 1, r + 1):
if (sorted_location[j][0] - sorted_location[m][0]) ** 2 < min_dist:
target_list.append(sorted_location[j])
else:
break
target_list.sort(key=lambda x: x[1])
for i in range(len(target_list) - 1):
for j in range(i + 1, len(target_list)):
if (target_list[i][1] - target_list[j][1]) ** 2 < min_dist:
dist = get_dist(target_list[i], target_list[j])
min_dist = min(min_dist, dist)
else:
break
return(min_dist)
if len(sorted_location) != len(set(sorted_location)):
print(0)
else:
print((solution(0, len(sorted_location) - 1)))
풀이
앞서 포스팅한 문제와 같은 분할 정복 문제로 '히스토그램'문제와 풀이 방식이 비슷하다. 다만 별들이 2차원 좌표이므로 생각해야할 부분이 조금 더 있다.
0) 먼저 x좌표가 가까운 점들끼리 비교를 하기 위해 점들을 x좌표를 기준으로 오름차순 정렬한다.
sorted_location.sort()
1) 이제 이 점들의 집합을 최소단위로 '분할'을 한다. 최소 단위인 별 한개(l=r)가 되었을 때는 거리를 계산할 수 없으므로 무한대인 float('inf')를 반환한다.
2) 최소단위가 아닐 때에는 중앙을 기준으로 왼쪽, 오른쪽으로 나눈 영역에서의 최솟값과 중앙값 m = (m + r) // 2 을 걸쳐서 생성된 영역에서의 최솟값 이 세 개의 값 중의 최솟값을 반환한다.
(이 부분은 이전 포스팅에 자세히 설명되어있다.)
이제 m을 걸친 영역에서의 최솟값을 구해보자.
2 - 1) 먼저 왼쪽과 오른쪽 영역에서 구한 최솟값 중 더 작은 값을 구한다.
min_dist = min(solution(l, m), solution(m + 1, r))
이제 가능한 점의 후보를 각 점의 x좌표와 m의 x좌표의 거리가 min_dist 미만인 점들로 추릴 수 있다.
최솟값을 찾아야 하기에 이미 min_dist 이상인 점들은 거리를 확인할 필요가 없기 때문이다.
2 - 2) 이제 m의 왼쪽, 오른쪽을 탐색해 나가면서 m의 x좌표와의 거리가 min_dist 미만인 점들을 후보로 넣어준다.
for i in range(m, l - 1, -1):
if (sorted_location[i][0] - sorted_location[m][0]) ** 2 < min_dist:
target_list.append(sorted_location[i])
else:
break
for j in range(m + 1, r + 1):
if (sorted_location[j][0] - sorted_location[m][0]) ** 2 < min_dist:
target_list.append(sorted_location[j])
else:
break2 - 3) 이제 이 부분이 포인트이다. 여기서 후보 점들을 y좌표를 기준으로 정렬해준다. 이미 x좌표는 비슷한 점들을 모았으니 y좌표가 가까운 점들을 비교했을 때 최솟값을 구할 수 있기 때문이다.
target_list.sort(key=lambda x: x[1])
이제 후보군 내 두 점간 거리를 계산한다.
이때 계산된 거리가 min_dist보다 작다면 min_dist를 최솟값으로 갱신해준다.
for i in range(len(target_list) - 1):
for j in range(i + 1, len(target_list)):
if (target_list[i][1] - target_list[j][1]) ** 2 < min_dist:
dist = get_dist(target_list[i], target_list[j])
min_dist = min(min_dist, dist)
else:
break만약 계산된 거리가 min_dist보다 크거나 같다면 이후에 나오는 점들과의 거리도 min_dist보다 크거나 같으므로 for문을 나간다. (y좌표로 이미 정렬이 되어있기 때문에 이후의 값은 지금의 y좌표와 크거나 같기 때문이다.)
모든 탐색이 끝나면 최솟값으로 갱신된 min_dist를 반환한다.
2 - 4) 만약 같은 점이 존재한다면 거리의 최솟값은 0이므로 같은 점이 존재하는지 확인해주고 있다면 0을 반환해준다.
if len(sorted_location) != len(set(sorted_location)):
print(0)
x좌표 정렬까지는 생각했지만 y좌표 정렬은 미처 생각하지 못해 애를 먹었던 문제이다.
히스토그램과 비슷한 방식으로 m, m + 1에서 좌우로 벌려나가며 x좌표 간 거리가 min_dist 미만인 점들을 대상으로 탐색을 했는데 시간초과가 나왔었다.
배울 것은 무궁무진하게 많다는 것을 다시 한 번 깨달았다.
피드백 환영합니다.
-끝-
