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.코드

4.배운점

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