[PS] 백준 2261번: 가장 가까운 두 점

|

문제

내가 이해한 문제 내용

좌표 평면에 여러개의 점이 주어질 때 가장 가까운 점 사이의 거리 제곱을 구하여라.

접근 방식

이 문제는 예전에 라인 스위핑으로 공부를 했었고 분할정복으로도 공부를 했었는데 라인 스위핑으로 푸는 방식이 훨씬 어렵기 때문에 다시 공부했다.

  • 처음 2개 좌표의 거리를 가장 가까운 거리 $d$로 초기화하고 그 좌표들을 후보에 넣는다.
  • 좌표들을 x좌표 기준 정렬한 후에 3번째 좌표부터 보면서 이전 후보 좌표들과의 거리가 $d$ 이상이면 커팅한다.
  • 위에서 커팅된 후보들에서 y좌표 기준으로 봐야 하는데 다시 정렬하게 되면 시간복잡도가 너무 안좋아져서 후보 좌표들을 넣을 컨테이너는 애초부터 set을 사용한다. set은 삽입/삭제/탐색이 모두 $O(lgN)$이므로 많이 줄일 수 있다.
  • y좌표 커팅할 때는 기존에 구한 $d$를 이용해서 현재 좌표가 $p$라면 $[p.y-d,p.y+d]$ 구간을 보면 된다. 해당 구간은 lower_boundupper_bound를 이용해서 구하며 $O(lgN)$이 소요된다.
  • 그렇게 x좌표와 y좌표 모두 커팅한 시점에서 $d$를 갱신한다.
  • 그 다음 좌표부터 위 과정을 반복해야 하며 $O(N)$이 걸린다.

어려웠던 점 & 배운 점

이 문제는 라인 스위핑이 너무 어려운 것 같다. 예전에 공부했는데도 다시 공부했고 다시 공부해도 상당히 어렵다;; 특히나 C++의 set이나 lower_bound, upper_bound 같은 컨테이너와 함수에서 번번히 막혀서 그 부분도 공부해야 했다.

시간복잡도

위에서 다 설명했고 최종으로 $O(NlgN)$

코드

사실상 코드는 백준님 설명을 공부한거라 똑같다고 보면 된다.

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>

struct Point{
    int x;
    int y;

    Point(){}
    Point(int x,int y):x(x),y(y){}

    bool operator<(const Point& p) const{
        if(y==p.y) return x<p.x;
        else return y<p.y;
    }
};

typedef std::set<Point>::iterator sit;

inline int dist(const Point& p1, const Point& p2){
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}

bool cmp(const Point& p1, const Point& p2){
    return p1.x<p2.x;
}

std::vector<Point> coor;
int n,x,y;

int main(void)
{
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%d%d",&x,&y);
        coor.push_back({x,y});
    }

    // x좌표 정렬
    std::sort(coor.begin(),coor.end(),cmp);

    // 후보
    std::set<Point> candidate{coor[0],coor[1]};
    int ans = dist(coor[0],coor[1]);
    int start = 0;

    for(int i=2; i<n; i++){
        Point now = coor[i];
        // 이전 후보들 검사
        while(start<i){
            int dx = now.x - coor[start].x;
            if(dx*dx > ans){
                candidate.erase(coor[start]);
                start++;
            } else break;
        }

        int d = (int)sqrt((double)ans)+1;

        Point lower = Point(-10001,now.y-d);
        Point upper = Point(10001,now.y+d);

        sit lit = candidate.lower_bound(lower);
        sit uit = candidate.upper_bound(upper);

        for(sit it=lit; it!=uit; it++){
            int d = dist(now,*it);
            ans = std::min(ans,d);
        }
        candidate.insert(now);
    }
    printf("%d",ans);
    return 0;
}