[BOJ 2261] 가장 가까운 두 점

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

2261번: 가장 가까운 두 점

---

Tag : Sweeping

 

풀이

\(N^2\)개의 점 중에 가장 가까운 두 점을 구해야하는 문제인데 \(\binom{N}{2}\)의 경우를 모두 따져보기엔 \(N\)이 굉장히 크다. 적어도 \(O(N\sqrt{N})\), 되도록 \(O(NlogN)\)까지 만들면 좋을 듯하다. 일단 \(N\)개의 점을 \(X\)기준으로 정렬해보자. 정렬한 후 모든 점을 순회하며 \(std::set\)에 현재 점과 \(X\)좌표의 차이가 현재까지의 최솟값 \(D\)보다 작은 점들만 가지고 있을 것이다. 이후 현재 점에서 \(Y\)좌표의 차이가 현재 최소인 \(D\)이하인 구간을 탐색할 것이다. 이 구간의 하한과 상한은 이분탐색을 통해 구할 수 있다.

(\(std::set::lower\_bound, std::set::upper\_bound)\) 

구한 구간의 모든 점과 현재 점의 거리로 최솟값을 갱신한다.

 

시간복잡도 : \(O(NlogN)\)

 

이 풀이가 왜 \(O(NlogN)\)에 돌아가는지 생각해보자. 스위핑을 진행하다 아무 점에서나 멈춰보자. 그럼 현재까지 갱신된 최소거리가 \(D\)이기 때문에 \(std::set\) 안에 들어있는 점들의 거리도 모두 각각 \(D\) 이상이다. 그리고 이분탐색으로 현재 점과의 \(Y\) 차이가 \(D\) 이하인 구간을 구하면 다음과 같은 구간이 나온다.

\(X\)거리가 \(D\)보다 큰 점들은 모두 제외됐고, \(Y\)거리가 \(D\)보다 큰 점들도 모두 제외됐기 때문에

위와 같은 직사각형에 속하는 점들만이 구간에 속하게 된다. 이 \(D*2D\)직사각형에 거리가 \(D\) 이상인 점들을 최대로 집어넣어봤자 5개정도가 나온다고 한다. 엄밀한 증명은 못하겠는데 넣어보려하면 더 넣긴 힘들다.

때문에 \(std::set\)에서 원소를 제거하는 것은 총 \(O(NlogN)\), 스위핑하는 원소의 개수는 \(O(N)\), 마지막으로 스위핑하는 원소마다 이분탐색을 하니 \(O(logN)\). 총합하면 \(O(NlogN)\)을 얻을 수 있다.

 

+ 솔직히 나는 못풀었는데 리프가 어거지로 풀이를 우겨넣어줘서 이해했다

 

전체 코드

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define endl '\n'
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N;cin>>N;vector<pair<int,int>>v(N);
    for(auto &[i,j]:v)cin>>i>>j;sort(all(v));
    int D=numeric_limits<int>::max();set<pair<int,int>>st;
    for(int i=0,p=0;i<N;i++){
        for(;p<i;p++){
            if((v[p].fi-v[i].fi)*(v[p].fi-v[i].fi)>D)st.erase({v[p].se,v[p].fi});
            else break;
        }
        int t=sqrt(D)+1;
        auto l=st.lower_bound({v[i].se-t,-1e9});
        auto r=st.upper_bound({v[i].se+t,1e9});
        for(auto it=l;it!=r;it++){
            D=min(D,(it->se-v[i].fi)*(it->se-v[i].fi)+(it->fi-v[i].se)*(it->fi-v[i].se));
        }
        st.insert({v[i].se, v[i].fi});
    }
    cout<<D<<endl;
}