[BOJ 2261] 가장 가까운 두 점

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

2261번: 가장 가까운 두 점

---

Tag : Sweeping

 

풀이

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

($std::set::lower\mathrm{\_}bound,std::set::upper\mathrm{\_}bound)$ 

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

 

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

 

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

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

위와 같은 직사각형에 속하는 점들만이 구간에 속하게 된다. 이 $D\ast 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;
}