[백준 2261][C++] 가장 가까운 두 점

가장 가까운 두 점

문제 분석 및 풀이

설계, 분석

• $n\le10^5$ 이므로 $O(NlogN)$까지 가능
• 스위핑의 전형적인 예시

• x값을 기준으로 정렬
• line을 한 방형으로 이동시키면서 line 근처의 점들이 후보가 되는지 판단 후 활성 집합에 넣음
  • 활성 집합은 y좌표를 기준으로 정렬
• 새 점을 만나면 새 점과의 거리가 d이상인 점을 제거
• 새 점과의 y차이가 d 이하인 범위만 탐색
• 거리 갱신 및 후보 집합에 넣기
• N번 순회마다 logN 탐색을 함
  • $O(NlogN)$
    
    

처음에 중복을 제거하고 문제를 풀었는데 정답이 나와서 모르고 있다가 여러 풀이를 보고 뭔가 잘못됨을 알았다. 이게 참 기묘한데
처음에는 중복을 제거하고 N번 반복문을 돌렸다. 이후에 코드를 수정하면서 '중복을 제거 했으니까 N번 말고 vector size로 돌려야지'라는 생각으로 고쳤더니 틀렸다.
문제는 두 점 사이의 거리가 가장 작은 쌍을 찾는 것이기 때문에 동일한 좌표면 거리가 0이라 이 점을 찾아야한다. 즉 중복을 제거하면 안된다.
처음 풀때 부터 중복을 제거 했었는데, N번을 돌리면서 '정의되지 않은 행동'이 어떻게 잘 해준 듯 하다. 정답을 맞추고도 한 번 살펴보는 습관을 들이자.

풀이

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

int N;

int main()
{
   cin >> N;
   
   long long d = LLONG_MAX;
   int left = 0;
   vector<pair<long long, long long>> pointVec;
   // y기준으로 정렬을 할거라 y,x 순으로 넣어야함
   set<pair<long long, long long>> activeSet;

   // s.
   for (int i=0; i<N; i++)
   {
    long long x,y;
    cin >> x >> y;
    pointVec.push_back({x,y});
   }

   sort(pointVec.begin(), pointVec.end());

   for (int i=0; i<pointVec.size(); i++)
   {
    long long newPointX = pointVec[i].first;
    long long newPointY = pointVec[i].second;

    //기존의 점들을 다시 확인
    //최소거리보다 긴 점들은 제외
    while((newPointX - pointVec[left].first)*(newPointX - pointVec[left].first) > d && left < i)
    {
        activeSet.erase({pointVec[left].second, pointVec[left].first});
        left++;
    }

    // 새로운 점의 y를 기준으로 +- d 안에 있는 후보만 탐색
    auto lower = activeSet.lower_bound({pointVec[i].second - sqrt(d), -INT_MAX});
    auto upper = activeSet.upper_bound({pointVec[i].second + sqrt(d), INT_MAX});

    for (auto it = lower; it != upper; ++it)
    {
        long long dy =  it->first - pointVec[i].second;
        long long dx =  it->second - pointVec[i].first;

        // 거리 갱신
        d = min (d, dy*dy + dx*dx);
        
    }
    activeSet.insert({pointVec[i].second, pointVec[i].first});
   }

   cout << d;

}