[백준] 3878 점 분리 (C++)

작성일 Edited on In , Views: Disqus:

문제

원문 링크 : https://www.acmicpc.net/problem/3878

평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 중 한 그룹에는 흰 점만 있어야 하고, 다른 그룹에는 검은 점만 있어야 한다.

아래 그림에서 제일 왼쪽 예제는 점선으로 표시된 직선으로 두 점을 나눌 수 있다. 하지만 나머지 예제는 직선으로 점을 분리할 수 없다.

흰 점과 검은 점의 좌표가 주어졌을 때, 직선으로 점을 분리할 수 있는지 없는지를 알아내는 프로그램을 작성하시오.

풀이 및 구현

흰 점과 검은 점을 직선을 통해 분리하기 위해선 두 점의 집합이 서로 겹친 부분이 있는지 확인해야 한다.

두 점의 집합이 서로 겹치는 부분이 존재하거나, 한 집합이 다른 집합 안에 포함되어 있다면 직선을 통해 분리 할 수 없고, 두 집합이 겹쳐 있지 않을 때만 직선으로 분리할 수 있다.

그러면 두 집합의 경계를 정해야 하는데 이를 위해 컨벡스 헐 알고리즘을 사용했다.

흰 점과 검은 점에 대해 각각의 컨벡스 헐을 구하면 흰 점의 컨벡스 헐 내부에는 모든 흰 점이 존재하고, 검은 점의 컨벡스 헐 내부에는 모든 검은 점이 존재한다.

즉 컨벡스 헐이 집합의 경계를 의미하기 때문에 두 컨벡스헐이 교차하는지 검사하면 직선을 통해 분리할 수 있는지 없는지 확인 할 수 있다.

컨벡스 헐을 만드는 알고리즘은 그라함 스캔 방식을 이용했다.

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
vector<point> ConvexHull(vector<point>& v) {
    sort(v.begin(), v.end());
    sort(v.begin() + 1, v.end(), [&](point& a, point& b) {
        int ccw = CCW(v[0], a, b);
        if (!ccw) return dist(v[0], a) < dist(v[0], b);
        return ccw > 0;
    });
    
    stack<int> st;
    st.push(0);

    for (int i = 1; i < (int)v.size(); i++) {
        if (st.size() < 2) {
            st.push(i);
            continue;
        }
        int a = st.top(); st.pop();
        int b = st.top();

        if (CCW(v[b], v[a], v[i]) > 0) st.push(a), st.push(i);
        else i--;
    }

    vector<point> c(st.size());
    for (auto& p : c) p = v[st.top()], st.pop();
    return c;
}

흰 점과 검은 점의 컨벡스 헐을 구한 다음엔 완전 탐색을 통해 두 컨벡스 헐의 변이 서로 교차하는 지 확인했다. 만약 어떤 두 변이 교차한다면 두 집합이 겹치는 부분이 있다는 뜻이므로 직선으로 분리할 수 없다는 의미가 된다.

1
2
3
4
5
6
7
8
9
10
11
vector<point> bc = ConvexHull(black), wc = ConvexHull(white);

// 두 컨벡스 헐이 교차하는지 판정
int bl = (int)bc.size(), wl = (int)wc.size();
for (int i = 0; i < bl; i++) {
    point p1 = bc[i], p2 = bc[(i + 1) % bl];
    for (int j = 0; j < wl; j++) {
        point p3 = wc[j], p4 = wc[(j + 1) % wl];
        if (intersect(p1, p2, p3, p4)) return false;
    }
}

교차 판정을 위해 선분 교차 문제에 사용한 알고리즘을 이용했다.

1
2
3
4
5
6
7
8
9
10
bool intersect(point& a, point& b, point& c, point& d) {
    int ab = CCW(a, b, c) * CCW(a, b, d);
    int cd = CCW(c, d, a) * CCW(c, d, b);
    if (!ab && !cd) {
        if (a > b) swap(a, b);
        if (c > d) swap(c, d);
        return a <= d && c <= b;
    }
    return ab <= 0 && cd <= 0;
}

만약 한 컨벡스 헐이 다른 컨벡스 헐에 포함되어 있다면 변이 서로 교차하지 않기 때문에 교차만으로는 확인할 수 없다.

따라서 두 컨벡스 헐을 구성하는 점들을 합쳐 새로운 컨벡스 헐을 구성해보았다.

이때 새롭게 만들어지는 컨벡스 헐이 기존 두 컨벡스 헐 중 겹치는 컨벡스 헐이 있다면 두 컨벡스 헐은 포함 관계가 되기 때문에 직선으로 분리할 수가 없다.

따라서 새로운 컨벡스 헐이 만들어졌다면 두 집합은 완전히 분리가 되어 있다는 의미이기 때문에 직선으로 분리할 수 있다고 판정할 수 있다.

1
2
3
4
5
6
// 두 컨벡스 헐로 새로운 컨벡스 헐을 만든다.
vector<point> sum(bc);
sum.insert(sum.end(), wc.begin(), wc.end());
vector<point> sumc = ConvexHull(sum);

return (sumc != bc && sumc != wc);

흰 점과 검은 점이 각각 100개 이하이기 때문에 위와 같은 방식으로 분리할 수 있는지 검사를 해도 시간이 충분하다.

코드

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> point;

int CCW(point& a, point& b, point& c) {
    ll ans = a.x * b.y + b.x * c.y + c.x * a.y - (b.x * a.y + c.x * b.y + a.x * c.y);
    if (ans > 0) return 1;
    if (ans < 0) return -1;
    return 0;
}

ll dist(point& a, point& b) {
    ll dx = b.x - a.x, dy = b.y - a.y;
    return (dx * dx + dy * dy);
}

vector<point> ConvexHull(vector<point>& v) {
    sort(v.begin(), v.end());
    sort(v.begin() + 1, v.end(), [&](point& a, point& b) {
        int ccw = CCW(v[0], a, b);
        if (!ccw) return dist(v[0], a) < dist(v[0], b);
        return ccw > 0;
    });

    stack<int> st;
    st.push(0);

    for (int i = 1; i < (int)v.size(); i++) {
        if (st.size() < 2) {
            st.push(i);
            continue;
        }
        int a = st.top(); st.pop();
        int b = st.top();

        if (CCW(v[b], v[a], v[i]) > 0) st.push(a), st.push(i);
        else i--;
    }

    vector<point> c(st.size());
    for (auto& p : c) p = v[st.top()], st.pop();
    return c;
}

bool intersect(point& a, point& b, point& c, point& d) {
    int ab = CCW(a, b, c) * CCW(a, b, d);
    int cd = CCW(c, d, a) * CCW(c, d, b);
    if (!ab && !cd) {
        if (a > b) swap(a, b);
        if (c > d) swap(c, d);
        return a <= d && c <= b;
    }
    return ab <= 0 && cd <= 0;
}

bool separate(vector<point>& black, vector<point>& white) {
    vector<point> bc = ConvexHull(black), wc = ConvexHull(white);

    // 두 컨벡스 헐이 교차하는지 판정
    int bl = (int)bc.size(), wl = (int)wc.size();
    for (int i = 0; i < bl; i++) {
        point p1 = bc[i], p2 = bc[(i + 1) % bl];
        for (int j = 0; j < wl; j++) {
            point p3 = wc[j], p4 = wc[(j + 1) % wl];
            if (intersect(p1, p2, p3, p4)) return false;
        }
    }

    // 두 컨벡스 헐로 새로운 컨벡스 헐을 만든다.
    vector<point> sum(bc);
    sum.insert(sum.end(), wc.begin(), wc.end());
    vector<point> sumc = ConvexHull(sum);
    
    return (sumc != bc && sumc != wc);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        vector<point> black(n), white(m);
        for (auto& [x, y] : black) cin >> x >> y;
        for (auto& [x, y] : white) cin >> x >> y;

        if (separate(black, white)) cout << "YES\n";
        else cout << "NO\n";
    }
}

후기

alt text

처음 제출할 땐 새로운 컨벡스 헐을 만들고 나서 완전히 일치하지 않을까봐 아래와 같이 정렬을 다시 하고 검사했다.

1
2
3
4
sort(bc.begin(), bc.end());
sort(wc.begin(), wc.end());
sort(sumc.begin(), sumc.end());
return (sumc != bc && sumc != wc);

곰곰히 생각해 봤을 때 컨벡스 헐을 만들 때 $x_{min}$을 기준으로 반시계 방향으로 돌아가면서 컨벡스 헐을 구성하기 때문에 정렬하지 않아도 일치할 것이라 생각해서 다시 제출했고 동일하다는 것을 확인할 수 있었다.

또한 정답을 맞춘 후 태그를 보니 “볼록 다각형 내부의 점 판정”이 따로 있는 것을 보아 관련 알고리즘도 공부해야겠다.