[Line Sweep] 가장 가까운 두 점 찾기

오늘 공부한 내용이다.

백준 블로그에서 먼저 작성해주신 내용을 보고 다시 차근차근 공부했다.

관련문제 보니까 풀려있어서 으잉...스러웠지만 코드가 이해가 안되는걸로 봐선 그때도 이해를 못했던 것 같다 ㅋㅋㅋ

풀이를 차근차근 읽어보니 어렴풋이 기억이 났지만 이번에 제대로 이해해보자 하는 마음으로 보았다.

 

 

www.acmicpc.net/blog/view/25

가장 가까운 두 점 찾기

 

 

 

 

 

 

<목표 코드 !>

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
struct Point {
    int x, y;
    Point() {
    }
    Point(int x, int y) : x(x), y(y) {
    }
    bool operator < (const Point &v) const {
        if (y == v.y) {
            return x < v.x;
        } else {
            return y < v.y;
        }
    }
};
bool cmp(const Point &u, const Point &v) {
    return u.x < v.x;
}
int dist(Point p1, Point p2) {
    return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}
int main() {
    int n;
    scanf("%d",&n);
    vector<Point> a(n);
    for (int i=0; i<n; i++) {
        scanf("%d %d",&a[i].x,&a[i].y);
    }
    sort(a.begin(), a.end(), cmp);
    set<Point> candidate = {a[0], a[1]};
    int ans = dist(a[0], a[1]);
    int start = 0;
    for (int i=2; i<n; i++) {
        Point now = a[i];
        while (start < i) {
            auto p = a[start];
            int x = now.x - p.x;
            if (x*x > ans) {
                candidate.erase(p);
                start += 1;
            } else {
                break;
            }
        }
        int d = (int)sqrt((double)ans)+1;
        auto lower_point = Point(-100000, now.y-d);
        auto upper_point = Point(100000, now.y+d);
        auto lower = candidate.lower_bound(lower_point);
        auto upper = candidate.upper_bound(upper_point);
        for (auto it = lower; it != upper; it++) {
            int d = dist(now, *it);
            if (d < ans) {
                ans = d;
            }
        }
        candidate.insert(now);
    }
    printf("%d\n",ans);
    return 0;
}

 

 

큰 흐름

1. 정렬된 노드들을 차례로 보면서 M번째 노드를 볼때 ,1~M-1번째까지의 노드들 사이의  최소거리인 d 라고 알고있다고 가정.

 

2. M번째 노드에서 앞의 노드들 중 x값의 차이가 d 이하이고 y 값 차이도 d 이하인 점들은 최소거리 d를 갱신 할 수 있는 후보군이다.

 

3. 후보군들과 M번째 노드를 비교하여 최소 거리 d 를 갱신한다. 

 

이런식으로 흘러간다. 

 

 

코드와 같이 설명

우선 입력된 노드들을 정렬한다. (x값정렬)

sort(a.begin(), a.end(), cmp);

 

후보군의 디폴트 값을 1,2번째 노드로 설정하고, 디폴트 최소거리 d를 구한다.

후보군의 y값의 자동정렬을 위해 set을 이용한다.(y값 거리비교를 위해 한번더 정렬해야하는 것을 방지.)

set<Point> candidate = {a[0], a[1]};
int ans = dist(a[0], a[1]);

 

현재 보고 있는 노드 i에서 x값의 차이가 d이상인 친구들을 지워 후보군에서 지운다.(디폴트 노드 제외,i는 2부터 시작.)

-> 후보군에서 지우기 위해 비교할때 후보군의 끝점은 항상 i-1번째 노드이다. start 변수를 사용하여 비교할 시작점을 저장해둔다.(x 값으로 정렬 되어 있음.)

int start = 0;
    for (int i=2; i<n; i++) {
        Point now = a[i];
        while (start < i) {
            auto p = a[start];
            int x = now.x - p.x;
            if (x*x > ans) {
                candidate.erase(p);
                start += 1;
            } else {
                break;
            }
        }
    ....
    }

 

남아있는 후보군 중 y값의 차이가 d 이하인 최소점과 최대점을 찾는다.

->이분 탐색 이용.

->후보군은 y값 정렬되어있다.

int d = (int)sqrt((double)ans)+1;
auto lower_point = Point(-100000, now.y-d);
auto upper_point = Point(100000, now.y+d);
auto lower = candidate.lower_bound(lower_point);
auto upper = candidate.upper_bound(upper_point);

 

정한 범위 내에 존재하는 점들과 현재 보고있는 점의 거리를 비교하여 최소거리인 d 값을 갱신한다.

for (auto it = lower; it != upper; it++) {
	int d = dist(now, *it);
	if (d < ans) {
	ans = d;
	}
}

 

마지막으로 후보군에 자신을 포함시킨다.(한번의 루프 마무리)

->이것을 (1,2번째 노드 제외)3번째 노드부터 마지막 노드까지 반복한다.

 candidate.insert(now);

 

반복문이 끝나면 최소거리 d 값을 구할 수 있다.

 

 

 

---

저글을 드디어 이해하게 됐다. 

매번 중간에 y값의 개념이 추가되는 부분부터 이해가 안됐었는데...

같이 공부하는 친구들과 이야기해보며 끝까지 정독을 할 수 있었다.

아직 구현은 나도 헤메면서 하겠지만 개념을 잡았다는것에 큰 의의가 생긴다.

알고리즘은 최근에 많이 하진못했지만(사실 글을 잘 안쓴거지만...)

조금씩이라도 어렵다고 느낀 문제들을 정리하고 풀이를 남겨봐야겠다.