BOJ)2261 가장 가까운 두 점

문제:icpc.me/2261

가장 가까운 두점을 N^2보다 적은 시간에 구해야하는 문제이다.

우선 점들을 x좌표 기준으로 스위핑해보자.

이후 x좌표가 증가하는 순서대로 점들을 볼건데

이미 본 점들은 y좌표 기준으로 정렬이 되도록 set에 삽입해준 후

지금까지의 최단거리가 d라면 현재 볼 점의 x좌표가 d이상 차이나거나 y좌표가 d이상 차이나는 점들을 제외하고 비교해준다.

x좌표가 정렬 된 순서로 보기 때문에 포인트를 잡아서 기록해두면 x좌표가 차이나는 점들은 set에서 제거해줄 수 있고

y좌표는 lower_bound와 upper_bound를 통하여 탐색 지점을 정해놓고 비교해주면 된다.

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
struct point {
    int x, y;
    point(int x, int y) :x(x), y(y) {}
    point() {}
    bool operator <(const point &p)const {
        if (y == p.y)return x < p.x;
        return y < p.y;
    }
};
bool cmp(const point &a, const point &b) {
    return a.x < b.x;
}
int getdist(point a, point b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
int n, x, y, d;
vector<point> vt;
set<point> st;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &x, &y);
        vt.push_back(point(x, y));
    }
    sort(vt.begin(), vt.end(), cmp);
    d = 2e9 + 10000000;
    int er = 0;
    for (int i = 0; i < n; i++) {
        for (int j = er; j < i; j++) {
            if ((vt[i].x - vt[j].x)*(vt[i].x - vt[j].x) >d) {
                st.erase(vt[j]);
                er++;
            }
            else
                break;
        }
        int dist = (int)sqrt((double)d) + 1;
        point lo = point(-100010, vt[i].y - dist);
        point hi = point(100000, vt[i].y + dist);
        auto l = st.lower_bound(lo);
        auto r = st.upper_bound(hi);
        for (auto it = l; it != r; it++) {
            d = min(d, getdist(*it, vt[i]));
        }
        st.insert(vt[i]);
    }
    printf("%d\n", d);
    return 0;
}