[Baekjoon] 2261. 가장 가까운 두 점

문제 설명

문제

2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 있다.

출력

첫째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다.

예제 입력 1

4
0 0
10 10
0 10
10 0

예제 출력 1

100

문제 풀이

# 분할정복

1. 모든 점을 x좌표 기준 정렬

   1-1. 동일한 점이 있다면 0을 반환

2. 중간 지점을 기준으로 왼쪽 영역과 오른족 영역으로 재귀적으로 분할

   2-1. 분할을 하다가 최소 단위인 점 한 개가 되었을 때는 거리를 계산할 수 없으므로 무한대를 반환한다.

3. merge 시, 좌측과 우측 영역에서의 최소 거리 중 더 작은 거리로 d를 초기화. d와 중앙 지점의 점 - 다른 점 사이의 거리를 비교.

   3-1. 중앙 지점의 점 - 다른 점 사이의 거리들 중 최소 거리가 될 수 있는 점은 x 좌표의 거리가 d 미만인 점이므로 해당 조건의 점들을 탐색하여 후보군 좌표들을 추출.

   3-2. 후보군 좌표들을 y좌표 기준으로 정렬

   3-3. 각각의 점을 한번씩 기준점으로 잡으면서 두 점 사이의 거리를 계산. 이 때, 계산된 거리가 d보다 작다면 d를 갱신한다.

   ​ 계산된 거리가 d보다 커지는 순간 해당 y좌표에 대한 탐색은 종료.

4. 계산된 최단 거리를 반환.

전체 코드입니다.

import sys
input = sys.stdin.readline

# 두 점 사이 거리 함수
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 = []

        ### 중앙의 점을 포함한 거리들 중 min_dist 미만의 거리가 있는지 탐색
        # x좌표 기준으로 내림차순 탐색 (중앙의 기준점과 다른 점 사이의 거리)
        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: # x 좌표 기준으로 정렬되어 있기 때문에 탐색 중지
                break
        # x좌표 기준으로 오름차순 탐색 (중앙의 기준점과 다른 점 사이의 거리)
        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: # x 좌표 기준으로 정렬되어 있기 때문에 탐색 중지
                break

        # y좌표 기준으로 오름차순 탐색 (임의의 두 점 사이의 거리)
        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: # y 좌표 기준으로 정렬되어 있기 때문에 해당 기준 y좌표에 대한 탐색 중지
                    break
        return min_dist


n = int(input())
sorted_location = [tuple(int(c) for c in input().split()) for _ in range(n)]
sorted_location.sort() # x 좌표 기준 정렬

if len(sorted_location) != len(set(sorted_location)): # 동일한 점이 있을 경우
    print(0)
else:
    print(solution(0,len(sorted_location)-1))