[ACM-ICPC Baek Joon] Closest pair of points problem

- 본 문제는 영어로 Closest pair of points problem라고 하며 한국어로는 최근점 점쌍 문제라고 부른다. 

- 본 문제에서 풀고자 하는 것은 2차원 좌표평면에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하는 것이다. 

- 사실 처음에는 그냥 2중 for문을 사용해서 구현하면 되는 단순한 문제인줄 알았지만, 계속 시간초과가 발생하여 무엇인 문제인지 찾아봤고, 이 문제는 부루투 포싱을 통해 가장 가까운 두 점을 찾는 문제가 아니라 분할정복 알고리즘을 구현하여 두 점을 찾는 문제임을 알게 되었다..

- 알고리즘에 대한 설명은 [1]에 나와있고, 내가 문제에 대한 상세는 [2]에 나와있다.

- 번거로움을 줄이기 위해 위키피디아[1]에 정리되어 있는 알고리즘의 개요를 그림으로 포스팅한다.

Baek Joon Online Judge[2]에 명시된 문제 원문은 아래와 같다.

 

그리고 내가 작성한 코드는 아래와 같다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include < stdlib.h > #include < algorithm >   using std::sort; using std::pair;   #define Min(a,b)    (((a) < (b)) ? (a) : (b)) #define Inf 999999999 #define SIZE 100000   typedef pair <int, int>  Pairs;   int eDist(Pairs mF, Pairs mS){     int x = (mS.first - mF.first);     int y = (mS.second - mF.second);     return (x*x) + (y*y); }     int seperator(Pairs * mPDot, const int idx){     Pairs * left;     Pairs * right;       int dist = Inf;     int dist1 = Inf;     int dist2 = Inf;     int dist3 = Inf;     int distMid = Inf;               if(idx == 3){         dist1 = eDist(mPDot[idx-3], mPDot[idx-2]);         dist2 = eDist(mPDot[idx-3], mPDot[idx-1]);         dist3 = eDist(mPDot[idx-2], mPDot[idx-1]);           dist = Min(dist1, dist2);         dist = Min(dist, dist3);     }       else if(idx == 2){         dist = eDist(mPDot[idx-2], mPDot[idx-1]);     }     else {         left = &(mPDot[0]);         right = &(mPDot[idx/2]);           dist = Min(seperator(left, idx/2), seperator(right, idx/2));               for(int i=(idx/2)-1; i > =0; i--){             for(int j=0; j < idx/2; j++){                 if( dist > ((left[i].first - right[j].first) * (left[i].first - right[j].first)) ){                     distMid = eDist(left[i], right[j]);                     dist = Min(dist, distMid);                 }                 else break;             }         }     }     return dist; }   int main(void){     int N = 0;     scanf("%d", &N);       Pairs pDot[SIZE];           int x, y;     for(int n=0; n < N; n++){         scanf("%d %d", &x, &y);         pDot[n] = Pairs (x, y);     }     sort(&(pDot[0]), &(pDot[0+N]));     printf("%d\n", seperator(pDot, N));       return 0; }

References:

[1] https://ko.wikipedia.org/wiki/최근접_점쌍_문제

[2] https://www.acmicpc.net/problem/2261