Closest Pair 최근접 점쌍 (2261 가장 가까운 두 점 )

http://acmicpc.net/problem/2261

2261번: 가장 가까운 두 점

1.접근

n이 100000이므로 O(N^2)으로는 풀 수 없다. 내가 아는 방법이 없는 것 같아서 구글링으로 

라인 스위핑 알고리즘과 분할정복을 통한 closest pair 방법이 있었는데 라인 스위핑이 아직 어려워서 분할정복으로 풀어보았다.

 

라인스위핑:www.acmicpc.net/blog/view/25

closet pair:casterian.net/archives/92

2.풀이

 

모든 부분을 분할해서 l,r,c 3가지 모든 부분을 구하는 것이다.

모든점의 거리의 최소값은 이 사이에 있을 수 밖에 없다.

 

우선 좌표값들을 x에 대해서 정렬시키고 mid좌표값으로 분할선을  잡아서 거리를 구하기 쉬운 2개씩 나눠질때까지 분할정복을 한다. 그에 따라서 최소값 d가 구해질 때마다 분할선 근처 값들만 찾아서 새로운 리스트를 만들고 그 리스트를 y에 대해 정렬한 후 d값을 갱신해 가면서 밑으로 올려서 쓸어 담는 식으로 최소값을 구한다.

 

3.코드

	import sys
	input=sys.stdin.readline
	INF=sys.maxsize
	def dist(a,b):
	return (a[0]-b[0])**2+(a[1]-b[1])**2
	def divide(start,end):
	if start==end:
	return INF
	elif end-start==1:
	return dist(arr[end],arr[start])
	mid=(start+end)//2
	temp=min(divide(start,mid),divide(mid,end))
	candicate=[]
	for i in range(start,end+1):
	if (arr[mid][0]-arr[i][0])**2<temp:
	candicate.append(arr[i])
	candicate.sort(key=lambda x:x[1])
	lc=len(candicate)
	for i in range(lc-1):
	for j in range(i+1,lc):
	dy=(candicate[i][1]-candicate[j][1])**2
	if dy<temp:
	temp=min(temp,dist(candicate[i],candicate[j]))
	else:
	break
	return temp
	n=int(input())
	arr=[]
	for i in range(n):
	arr.append(tuple(map(int,input().split())))
	arr.sort()
	print(divide(0,len(arr)-1))

view raw 2261 가장 가까운 두점.py hosted with ❤ by GitHub

4.배운점

• closet pair은 O(nlog^2n)의 시간복잡도를 가진다.
• y값에 대해서 정렬했을 때 n^2이라고 생각할 뻔 했지만 y좌표도 최소값 사이의 값만 보면 된다.
• 라인스위핑은 나중에 더 공부해야겠다 set에서 이해가 잘 안 되었다.