ks1ksi

백준 2261번 가장 가까운 두 점

3 min read

문제 링크

좌표 기준으로 정렬 후 앞에서부터 스위핑. 지금까지 찾은 최단 거리를 , 이번에 거리를 잴 점을 라 할 때, 좌표, 좌표가 와 이상 차이나는 점은 확인할 필요가 없다. set에 좌표 기준으로 점을 넣어 두면서, 좌표가 보다 멀리 있는 점은 삭제한다. 인 점 의 범위를 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 대비 강연은 하러 오신다는데 넘 신기하다. 블로그 잘 보고 있다고 얘기해야겠다.

Graph View