2261번: 가장 가까운 두 점

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

#include<stdio.h>
#include<algorithm>
#include<set>
#define x first
#define y second
using namespace std;
pair<int, int> p[100000];
set<pair<int, int> > st;
int n;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &p[i].x, &p[i].y);
    sort(p, p + n);
    int res = 1e9, rt = sqrt(res);
    for (int i = 0, h = 0; i < n; i++) {
        while (p[i].x - p[h].x>rt) st.erase({ p[h].y, p[h++].x });
        for (set<pair<int, int> >::iterator it = st.lower_bound({ p[i].y - rt, -1e9 });
        it != st.end() && it->x <= p[i].y + rt; it++) {
            int d = (p[i].x - it->y)*(p[i].x - it->y) + (p[i].y - it->x)*(p[i].y - it->x);
            if (d < res) {
                res = d;
                rt = sqrt(d);
            }
        }
        st.insert({ p[i].y, p[i].x });
    }
    printf("%d", res);
    return 0;
}