티스토리 뷰

알고리즘 관련/BOJ

BOJ)2261 가장 가까운 두 점

JASON 자손9319 2017. 7. 9. 18:52

문제:icpc.me/2261


가장 가까운 두점을 N^2보다 적은 시간에 구해야하는 문제이다.


우선 점들을 x좌표 기준으로 스위핑해보자.


이후 x좌표가 증가하는 순서대로 점들을 볼건데


이미 본 점들은 y좌표 기준으로 정렬이 되도록 set에 삽입해준 후


지금까지의 최단거리가 d라면 현재 볼 점의 x좌표가 d이상 차이나거나 y좌표가 d이상 차이나는 점들을 제외하고 비교해준다.


x좌표가 정렬 된 순서로 보기 때문에 포인트를 잡아서 기록해두면 x좌표가 차이나는 점들은 set에서 제거해줄 수 있고


y좌표는 lower_bound와 upper_bound를 통하여 탐색 지점을 정해놓고 비교해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
struct point {
    int x, y;
    point(int x, int y) :x(x), y(y) {}
    point() {}
    bool operator <(const point &p)const {
        if (y == p.y)return x < p.x;
        return y < p.y;
    }
};
bool cmp(const point &a, const point &b) {
    return a.x < b.x;
}
int getdist(point a, point b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
int n, x, y, d;
vector<point> vt;
set<point> st;
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d"&x, &y);
        vt.push_back(point(x, y));
    }
    sort(vt.begin(), vt.end(), cmp);
    d = 2e9 + 10000000;
    int er = 0;
    for (int i = 0; i < n; i++) {
        for (int j = er; j < i; j++) {
            if ((vt[i].x - vt[j].x)*(vt[i].x - vt[j].x) >d) {
                st.erase(vt[j]);
                er++;
            }
            else
                break;
        }
        int dist = (int)sqrt((double)d) + 1;
        point lo = point(-100010, vt[i].y - dist);
        point hi = point(100000, vt[i].y + dist);
        auto l = st.lower_bound(lo);
        auto r = st.upper_bound(hi);
        for (auto it = l; it != r; it++) {
            d = min(d, getdist(*it, vt[i]));
        }
        st.insert(vt[i]);
    }
    printf("%d\n", d);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11985 오렌지 출하  (0) 2017.07.24
BOJ)10637 Minimum Spanning Tree  (0) 2017.07.21
BOJ)2261 가장 가까운 두 점  (1) 2017.07.09
BOJ)5038 Flight Planning  (0) 2017.07.09
BOJ)8872 빌라봉  (0) 2017.07.08
BOJ)1444 숌 언어  (0) 2017.07.05
댓글
  • 프로필사진 mic1021 시간복잡도가 O(NlgN)라고 알고있는데 이해가 안가서 질문드립니다.
    위 코드에서 47~48번째 줄을 보면 st에 있는 좌표들을 전부다 보면서 탐색하는데
    최대 st에 원소가 N 개 들어갈수 있으니 최악의 경우엔 O(N^2)이 나오지 않을까요?
    2018.07.31 15:25
댓글쓰기 폼