[백준] 2261번: 가장 가까운 두 점 | C++

2261번: 가장 가까운 두 점

브루트포스로 O(N^2) 시간에 해결할 수 있지만, O(NlogN)으로 푸는 방법을 알아보고자 한다.

 

 

정답코드

1. x좌표 기준으로 오름차순 정렬한다.

2. 0번째와 1번째 거리를 최소 거리(min_d)라고 가정한다.

3. 현재 살펴보는 좌표가 i번째 (x, y)라고 하면 [x - min_d, x] 범위에 해당하는 좌표를 "더 가까울 수 있는" 좌표 후보에 추가한다.

4. [y - min_d, y + min_d] 에 해당하는 좌표들만 후보로 삼는다.

 

[y-min_d, y+min_d]에 좌표가 아래와 같이 많다고 가정하자.

lower_bound와 upper_bound를 사용하면 쉽게 범위 내 좌표만 살필 수 있다. 

 

y좌표 기준으로 정렬을 수행해도 된다. 코드에서 set 자료구조를 사용하기 때문에 lower_bound와 upper_bound를 사용했다. STL set은 레드블랙트리로 구현됐기 때문!

 

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>
#define MAX 100000
#define fse(A,B,C) for(int i=A;i<B;i+=C)
using namespace std;
class Point{
    public:
    int x; int y;
    Point(int x,int y){
        this->x=x; this->y=y;
    }
    bool operator < (const Point &v) const {
        if(y == v.y){
            return x < v.x;
        }else{
            return y < v.y;
        }
    }
};
int distance(Point a, Point b){
    int x=a.x-b.x;
    int y=a.y-b.y;
    return x*x + y*y;
}
bool comp(const Point &a, const Point &b){
    return a.x < b.x;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int N;
    cin>>N;
    vector<Point> dots;
    fse(0,N,1){
        int a,b;
        cin>>a>>b;
        dots.push_back(Point(a,b));
    }

    sort(dots.begin(), dots.end(), comp); // (1) x축 정렬

    set<Point> candi={dots[0], dots[1]};
    int min_d=distance(dots[0], dots[1]); (2)
    int index=0;
    for(int i(2);i<N;i++){
        if(min_d==0) break;

        Point now = dots[i];
        while(index < i){ 
            auto target=dots[index];
            int tmp = now.x - target.x;
            if(tmp*tmp > min_d){ // (3) [x-d, x] 범위에 포함되는지?
                candi.erase(target); // x-d 미만인 애들 삭제
                index++;
            }else{
                break;
            }
        }

        int d = (int)sqrt((double)min_d)+1;
        auto lower_y = candi.lower_bound(Point(-MAX, now.y-d));
        auto upper_y = candi.upper_bound(Point(MAX, now.y+d));
        for(auto it=lower_y; it!=upper_y; it++){ // (4) [y-d, y+d] 범위 내 좌표 판별
            int d=distance(now, *it);
            min_d=min(min_d, d);
        }
        candi.insert(now);
    }
    cout<<min_d;
}

pair<int,int>로 하니까 시간초과가 난다. 구조체를 만드니까 시간초과가 나지 않음..

 

 

 

참고

https://www.acmicpc.net/blog/view/25