# 문제
2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.
# 입력
첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 있다.
# 출력
첫째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다.
# n개의 점을 입력 받아 2차원 리스트로 저장
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
arr.sort() # x좌표를 기준으로 정렬
(x 좌표 차이의 제곱 + y 좌표 차이의 제곱) ** 1/2
요로케 해주면 된다.** 1/2
는 노놉!def get_dist(a, b): # 두 점 사이의 거리를 구하는 함수
return (a[0]-b[0])**2+(a[1]-b[1])**2
sys.maxsize
를 때려버린당def get_min(start, end):
if start == end: # 점이 하나인 경우, 최대값 반환
return sys.maxsize
if end - start == 1: # 점이 두 개인 경우, 두 점 사이의 거리 반환
return get_dist(arr[start], arr[end])
mid = (start + end) // 2 # 중간 지점 계산
# 왼쪽 절반과 오른쪽 절반을 각각 재귀적으로 호출
min_dist = min(get_min(start, mid), get_min(mid, end))
쪼개지는 부분에 절묘하게 답이 존재할 수도 있다.
그래서 쪼개지는 부분도 검증해줘야 한다. 🙁😠
위에서 일단 min_dist
를 구했으니까,
쪼개진 지점인 arr[mid]
를 중심으로 왼쪽 오른쪽으로 -min_dist ~ +min_dist
범위 안에 드는 점들만 찾아서 candidates
에 모은다.
범위 안에 드는 점들만 찾기 👉🏻(arr[mid][0] - arr[i][0])**2 < min_dist
💡 이 거리가 제곱되어있는 값이라는 것 잊지말자
# 가운데 점(mid)을 기준으로 거리가 min_dist보다 작은 점들을 candidates 리스트에 추가
candidates = []
for i in range(start, end+1):
if (arr[mid][0] - arr[i][0])**2 < min_dist:
candidates.append(arr[i])
# candidates 리스트를 y좌표를 기준으로 정렬
candidates.sort(key=lambda x: x[1])
# candidates 리스트 내에서 최소 거리를 구함
for i in range(len(candidates)-1):
for j in range(i+1, len(candidates)):
candidates
를 만들 때 했던 것처럼, y좌표도 차이의 제곱이 min_dist
를 넘어가면 반복을 멈춘다. (어차피 더 멀어서 볼 것도 없음😋) # y좌표 차이가 min_dist보다 작은 경우에만 최소 거리 계산
if (candidates[i][1] - candidates[j][1])**2 < min_dist:
min_dist = min(min_dist, get_dist(
candidates[i], candidates[j]))
else:
break
전체 코드
import sys
n = int(input())
# n개의 점을 입력 받아 2차원 리스트로 저장
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
arr.sort() # x좌표를 기준으로 정렬
def get_dist(a, b): # 두 점 사이의 거리를 구하는 함수
return (a[0]-b[0])**2+(a[1]-b[1])**2
def get_min(start, end):
if start == end: # 점이 하나인 경우, 최대값 반환
return sys.maxsize
if end - start == 1: # 점이 두 개인 경우, 두 점 사이의 거리 반환
return get_dist(arr[start], arr[end])
mid = (start + end) // 2 # 중간 지점 계산
# 왼쪽 절반과 오른쪽 절반을 각각 재귀적으로 호출하여 최소 거리를 구함
min_dist = min(get_min(start, mid), get_min(mid, end))
# 가운데 점(mid)을 기준으로 거리가 min_dist보다 작은 점들을 candidates 리스트에 추가
candidates = []
for i in range(start, end+1):
if (arr[mid][0] - arr[i][0])**2 < min_dist:
candidates.append(arr[i])
# candidates 리스트를 y좌표를 기준으로 정렬
candidates.sort(key=lambda x: x[1])
# candidates 리스트 내에서 최소 거리를 구함
for i in range(len(candidates)-1):
for j in range(i+1, len(candidates)):
# y좌표 차이가 min_dist보다 작은 경우에만 최소 거리 계산
if (candidates[i][1] - candidates[j][1])**2 < min_dist:
min_dist = min(min_dist, get_dist(
candidates[i], candidates[j]))
else:
break
return min_dist
print(get_min(0, n-1))