[백준] [C++] 2261번 가장 가까운 두 점 (sweeping)

1. 문제

 

2261번: 가장 가까운 두 점 (acmicpc.net)

2261번: 가장 가까운 두 점

 

 

아래 문제 풀이를 보고 작성하였다.

*[C/C++] 백준 2261번 - 가장 가까운 두 점 (라인 스위핑) :: 코딩 공부 일지 (tistory.com)

2. 풀이

set과 mindist의 정의가 다음과 같을때 큰 틀은 다음과 같다.

 

set: 고려될 수 있는 점집합

mindist: 현재까지 가장 짧은 두점 거리

1) x축 기준으로 정렬 2) 첫 두점을 기준으로 mindist 설정 3) set에 첫 두점을 y 축 기준으로 삽입  4) 인덱스 2부터 고려대상인 점집합과의 거리 구한후 mindist업데이트, set에 포함

 

x축 기준으로 정렬, x가 작은것부터 순차적으로

    => 만약 현재 조사하고 있는 점 x와 set의 가장 왼쪽점 x 의 차이가 mindist보다 크다면,

         이후의 점들은 물론이고 이 점은 더이상 고려대상이 아님을 의미

    => set에서 제외

 

set 에 y축 기준으로 삽입

    => set은 bst자료구조를 사용한다. 따라서 y축 기준으로 자동적으로 정렬되고,

        y축에서 현재 조사하고있는점에서 mindist 이내의 점들의 범위를 구하기 쉬워진다. 

 

 

 

 

3. 코드

 

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
 
using namespace std;
int n;
vector<pair<int, int> > xy;
 
 
int dist(const pair<int, int>& a, const pair<int, int>& b) {
    return (a.first-b.first)*(a.first-b.first) + (a.second - b.second)*(a.second - b.second);
}
 
int sol() {
    set<pair<int, int> > s;
    int minDist = dist(xy[0], xy[1]), idx = 0;
    s.insert( {xy[0].second, xy[0].first} );
    s.insert( {xy[1].second, xy[1].first} );
 
    for(int i = 2; i < xy.size(); i++) {
        while(idx < i) {
            int tmp = xy[i].first - xy[idx].first;
            if(tmp*tmp < minDist) {
                break;
            }
            else {
                s.erase({xy[idx].second, xy[idx].first});
                idx++;
            }
        }
        auto start = s.lower_bound(make_pair(xy[i].second - sqrt(minDist), INT32_MIN));
        auto end = s.upper_bound(make_pair(xy[i].second + sqrt(minDist),  INT32_MAX));
        for(auto it = start; it != end; it++) {
            minDist = min(minDist, dist(xy[i], {it->second, it->first}));
        }
 
        s.insert({xy[i].second, xy[i].first});
    }
 
    return minDist;
}
 
int main() {
    cin>>n;
    xy = vector<pair<int, int> >(n);
    
    for(int i = 0; i < n; i++) {
        int a, b;
        cin>>a>>b;
        xy[i].first = a;
        xy[i].second = b;
    }
    sort(xy.begin(), xy.end());
    cout<<sol();
}