[2261번] 가장 가까운 두 점

문제 출처 :

https://www.acmicpc.net/problem/2261

알고리즘 분석 :

문제 해결에 필요한 사항

1. 라인 스위핑

2. Map

이 문제는 아직 내 힘으로는 풀기가 힘들어 다른 사람들의 풀이를 참고하여 공부한 내용이다.

이 소스 코드의 동작은 다음과 같다.

1. 모든 x,y 값을 받아내고, x에 대해 정렬을 한다.

2. 정렬 후 가장 작은 x값 두 점의 거리를 구한다. 이 두 점간의 거리를 최단 거리라고 처음에 가정한다.

2. 이제 for문을 통해 한 점을 잡고, 한 점과 last(0부터 시작)점을 잡아 두점간의 x거리를 구하는데

이 x간의 거리가 최단 거리보다 크면 map에서 지워준다.(라인 스위핑)

3. 최단 거리보다 짧은 거리가 나온 점이 있다면 break를 해주고(현재 이 점은 최단 거리보다 거리가 짧게 나올 수 있는 후보이다.)

그 점을 기준으로 lower_bound, upper_bound를 이용하여 이 점을 기준으로 

현재 최단 거리의 길이를 가지는 사각형 내부의 모든 점의 최솟값을 조사한다.

4. 최솟값을 찾아내고, 현재 점 i를 map에 추가시켜주며 반복한다.

아직 Line Sweeping은 조금 어렵기도하고, 더 공부해야 될 부분인 것 같다.

참고로 이 문제를 Divide And Conquer 방법으로도 풀 수 있다고 한다.

소스 코드 : 

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 76 77 78 79 80 81 82 83 84 85 86 87 88 89

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <map> #include <vector>   #define inf 100000000   using namespace std;   typedef pair<int, int> pii;   map<pii, int> mp;   double getDist(pii a, pii b) {     int x = a.first - b.first;     int y = a.second - b.second;       return (double)(x*x + y*y); }   int main() {     int n;     scanf("%d", &n);       vector<pii> vc;       for (int i = 0; i < n; i++)     {         int x, y;         scanf("%d %d", &x, &y);           vc.push_back({ x,y });     }       // x에 대해 정렬     sort(vc.begin(), vc.end());       // 처음 두 값 map에 추가(y, x 순서)     mp[{vc[0].second, vc[0].first}] = 1;     mp[{vc[1].second, vc[1].first}] = 1;       // 최솟값 초기화     double ans = getDist(vc[0], vc[1]);       int last = 0;       for (int i = 2; i < n; i++)     {         // while문은 최솟값보다 x간의 거리가 더 큰 것을 제거하는 과정         // x간의 거리가 최솟값 보다 더 크면 y값을 비교할 필요가 없다.         while (last < i)         {             // i > last             int dx = vc[i].first - vc[last].first;               // 최솟값이 더 크거나 같으면 break;(검사여지 없음)             if (dx * dx <= ans)                 break;               // 최솟값 보다 더 큰 last에 해당하는 mp값 제거             mp.erase({ vc[last].second, vc[last].first });             last++;         }           // ans의 실제 거리         int limit = sqrt(ans);           // y좌표를 봤을 때 현재 알고있는 최솟값 기준으로 답일 수 있는 영역 설정         auto lo = mp.lower_bound({ vc[i].second - limit, -inf });         auto up = mp.upper_bound({ vc[i].second + limit,  inf });           // 그 영역 내에서 최솟값         for (auto it = lo; it != up; it++)             ans = min(ans, getDist({ it->first.second, it->first.first }, vc[i]));           // map에 추가         mp[{vc[i].second, vc[i].first}] = 1;     }       printf("%d", (int)ans);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus