2261 가장 가까운 두 점

Link

---

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

Detail

---

점 개수가 100000이다. $O(N^2)$ 으로 풀 수 없는 문제다.

Sweeping 기법을 사용해서 문제를 해결한다면 다음과 같은 과정을 거친다.

• 모든 좌표를 x값 기준으로 정렬한다. $O(NlogN)$
• Min_dist 값 하나를 잡아두고 스위핑을 돌린다. 이 값보다 x값이 차이가 나면 left를 끌어올린다. $O(N)$
  • Right값을 하나 갱신해 줄 때마다, 추가되는 후보 점들을 set에 y좌표 기준으로 정렬해서 넣어둔다. $O(logN)$
  • 추가로 Min_dist값 이내에 해당되는 값들만 binary_search로 찾아서 값을 추가한다. $O(logN)$

시간 복잡도 = $O(NlogN)+O(N)\ast O(2logN)\approx O(NlogN)$

Code

---

#include<bits/stdc++.h>
 
using namespace std;
 
using pos = pair<int, int>;
using ll = long long;
 
pos inline get_input() {
    pos new_pos;
    cin >> new_pos.first >> new_pos.second;
    return new_pos;
}
 
pos inline flip(const pos& ori) {
    return make_pair(ori.second, ori.first);
}
 
ll inline dist_sqr(const pos& one, const pos& two) {
    ll dx = (ll)one.first - two.first;
    ll dy = (ll)one.second - two.second;
    return dx*dx + dy*dy;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int n; cin >> n;
    
    vector<pos> dots(n);
    set<pos> y_sorted;
    for(auto& p : dots) {
        p = get_input();
    }
       
    // start sweeping
    sort(dots.begin(), dots.end());
    
    y_sorted.insert(flip(dots[0]));
    y_sorted.insert(flip(dots[1]));
    ll min_dist = dist_sqr(dots[0], dots[1]);
    
    int l = 0, r = 1;
    for(r = 2; r < n; r++){
        
        // x값의 차이가 min_dist 이내인 값들로만 스위핑 영역 구성
        while(l < r) {
            ll x_diff = dots[r].first - dots[l].first;
            if(x_diff * x_diff <= min_dist) break;
            
            y_sorted.erase(flip(dots[l++]));
        }
        
        // y값이 min_dist이내인 애들로만 작성
        ll sqrt_dist = static_cast<ll>(sqrt(min_dist));
        pos hi = {dots[r].second + sqrt_dist, INT_MAX};
        pos lo = {dots[r].second - sqrt_dist, INT_MIN};
        auto top_iter = y_sorted.upper_bound(hi);
        auto btm_iter = y_sorted.lower_bound(lo);
        
        for(auto it = btm_iter; it != top_iter; it++) {
            ll dist = dist_sqr(flip(*it), dots[r]);
            min_dist = min(min_dist, dist);
        }
        
        // 비교대상 영역에 r값 추가
        y_sorted.insert(flip(dots[r]));
    }
    
    cout << min_dist << '\n';
    
    
    return 0;
}