[Baekjoon] 2261번 : 가장 가까운 두 점

1. 문제

https://www.acmicpc.net/problem/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

2. 핵심 아이디어

• 모든 점 x좌표를 기준으로 정렬
• 점들의 중앙값을 기준으로 양분할
• 2개 까지 분할되면 점 사이의 최소 거리를 찾음
• 해당 거리보다 x좌표끼리 가까운 것만 후보 점으로 등록
• y좌표 기준으로도 정렬
• y좌표 차이가 최소 거리보다 낮은 것들만 대상으로 거리 계산

3. Python 문제풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]

arr.sort()

def get_distance(p1, p2) :
  return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

def dac(start, end) :
  if start == end :
    return float('inf')
  if end - start == 1 :
    return get_distance(arr[start], arr[end])

  mid = (start + end) // 2
  min_distance = min(dac(start, mid), dac(mid, end))
  target = []
  for i in range(start, end+1) :
    if (arr[mid][0] - arr[i][0]) ** 2 < min_distance :
      target.append(arr[i])

  target.sort(key = lambda x : x[1])

  t = len(target)
  for i in range(t-1) :
    for j in range(i+1, t) :
      if (target[i][1] - target[j][1]) ** 2 < min_distance :
        min_distance = min(min_distance, get_distance(target[i], target[j]))
      else :
        break

  return min_distance

print(dac(0, n-1))

4. Java 문제풀이