백준 2261번 가장 가까운 두 점

문제 링크

$x$좌표 기준으로 정렬 후 앞에서부터 스위핑. 지금까지 찾은 최단 거리를 $d$, 이번에 거리를 잴 점을 $p$라 할 때, $x$좌표, $y$좌표가 $p$와 $d$이상 차이나는 점은 확인할 필요가 없다. set에 $y$좌표 기준으로 점을 넣어 두면서, $x$좌표가 $d$보다 멀리 있는 점은 삭제한다. $p_y - d \le q_y \le p_y + d$ 인 점 $q$의 범위를 lower_bound()로 찾아서 최단 거리를 계산한다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

struct Compare {
    bool operator() (const pair<ll, ll>& p1, const pair<ll, ll>& p2) const {
        return make_pair(p1.second, p1.first) < make_pair(p2.second, p2.first);
    }
};

ll square(ll x) {
    return x*x;
}

ll powdist(pair<ll, ll> p1, pair<ll, ll> p2) {
    return square(p1.first - p2.first) + square(p1.second - p2.second);
} 

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

    int n;
    cin >> n;
    vector<pair<ll, ll>> v(n);
    for (auto& [a, b] : v) {
        cin >> a >> b;    
    }
    sort(v.begin(), v.end());

    set<pair<ll, ll>, Compare> st;
    ll dist = powdist(v[0], v[1]);
    st.emplace(v[0]);
    st.emplace(v[1]);
    for (int i = 2, j = 0; i < n; i++) {
        while (j < i && square(v[i].first - v[j].first) >= dist) {
            st.erase(v[j++]);
        }

        ll d = sqrt(dist) + 5;
        auto start = st.lower_bound({-10000, v[i].second - d});
        auto end = st.upper_bound({10000, v[i].second + d});

        for (auto it = start; it != end; it++) {
            dist = min(dist, powdist(v[i], *it));
        }

        st.emplace(v[i]);
    }

    cout << dist;

    return 0;
}

set는 operator()를 오버로딩하는 Compare 구조체를 받는다. 적절한 코드를 작성하여 set에 있는 원소가 정렬되는 순서를 조절할 수 있다.

IOI KOREA 유튜브의 나정휘 선생님 강의를 참고했다.

다음주 목요일 (5월 4일)에 나정휘 선생님이 우리학교에 ICPC 대비 강연은 하러 오신다는데 넘 신기하다. 블로그 잘 보고 있다고 얘기해야겠다.