가장 가까운 두 점

2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.

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

점을 x 좌표 기준으로 정렬한 다음, x좌표가 현재까지의 최소 거리 범위 안에 있는 점 중 y좌표도 현재까지의 최소 거리 범위 안에 있는 점들을 순회하며 최소값을 구하면 풀린다.

같은 위치의 점이 여러개 있을 것을 고려해서 multiset을 썼었는데 multiset을 쓰니 시간초과가 났다… 어차피 같은 위치의 점은 정렬 후에도 바로 옆에 붙어있을 것이고, 이 때문에 항상 S라는 set에 이전 점이 남아있는 동안 이후 점과 비교하게 되어 상관없다.

#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
pair<int, int> dot[100001];

long long dist(pair<int, int> d1, pair<int, int> d2) {
    return pow(abs(d1.first-d2.first), 2) + pow(abs(d1.second-d2.second), 2);
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin>>n;
    for (int i=0;i<n;i++) cin>>dot[i].first>>dot[i].second;
    sort(dot, dot+n);
    long long res=dist(dot[0], dot[1]);

    auto cmp = [](pair<int, int> a, pair<int, int> b) {
        if(a.second == b.second) return a.first > b.first;
        return a.second < b.second;
    };
    set<pair<int, int>, decltype(cmp)> S(cmp);

    S.insert(dot[0]);
    int l=0;
    for (int i=1;i<n;i++) {
        long long d = sqrt(res)+1;
        while (dot[i].first-dot[l].first>d && l<n) {
            S.erase(dot[l++]);
        }
        auto l = S.lower_bound(make_pair(1000000, dot[i].second-d));
        auto r = S.lower_bound(make_pair(-1000000, dot[i].second+d));
        for (auto it=l;it!=r;it++) {
            res = min(res, dist(*it, dot[i]));
        }
        S.insert(dot[i]);
    }
    cout<<res;
}