[백준] 24235 유산 (C++)

작성일 In , Views: Disqus:

문제

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

조상때부터 대대로 물려받던 땅이 있다. 땅이 매우 크기 때문에
$N$개 위치를 좌표평면 위에 점으로 표시를 해놓았다. 땅은
$N$개의 점을 모두 포함하는 가장 작은 볼록다각형이다.

이 땅을 두 명한테 나눠주려고 한다. 나눠주는 땅의 넓이가 같도록 해야 싸움이 일어나지 않을 것이기 때문에
$y$축이랑 평행한 직선 $x = a$를 그어 나눠지는 두 땅의 넓이가 같도록 하려고 한다.

[그림 1]처럼 좌표평면에 9개 점이 존재한다고 가정해보자.

img.png

[그림 1] 9개의 점을 좌표평면에 표시

땅을 표시하는 좌표평면 정보에서 땅은 9개의 점을 모두 포함하는 가장 작은 볼록다각형이기 때문에 [그림 2]와 같다.

img_1.png

[그림 2] 좌표평면에 땅에 해당하는 부분 표시

두 명이 이 땅을 넓이가 같도록 나눠야 하기 때문에 [그림 3]처럼 직선을 그어 두 땅의 넓이가 같도록 구분하면 된다.

img_2.png

[그림 3] 두 땅의 넓이가 같도록 $x = a$ 직선으로 구분

땅의 정보가 주어졌을 때 같은 면적의 땅을 나눌 수 있도록 $a$의 값을 찾아주자.

풀이 및 구현

문제에 대한 접근은 어렵지 않다.

주어진 땅의 넓이가 $N$개의 점을 모두 포함하는 가장 작은 볼록다각형이라고 주어졌으니 주어진 점으로 컨벡스 헐을 만든다.

땅을 나눌 때는 $y$축과 평행한 직선으로 땅을 나누면 되기 때문에 컨벡스 헐에서 $x_{min}$과 $x_{max}$를 구한 뒤, 이를 lo, hi로 놓고 이분 탐색을 돌리면 된다.

이때 땅의 넓이는 부동 소수점으로 표현되기 때문에 오차에 유의하여 돌아야 한다.

컨벡스헐 구하기

컨벡스 헐을 구하는 부분은 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
double area(point& a, point& b, point& c) {
    return (a[0] * b[1] + b[0] * c[1] + c[0] * a[1] - (b[0] * a[1] + c[0] * b[1] + a[0] * c[1])) / 2;
}

int CCW(point& a, point& b, point& c) {
    double ans = area(a, b, c);
    if (ans > 0) return 1;
    if (ans < 0) return -1;
    return 0;
}

int dist(point& a, point& b) {
    int dx = b[0] - a[0], dy = b[1] - a[1];
    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> ch(st.size());
    for (auto& p : ch) p = v[st.top()], st.pop();
    return ch;
}

이후 넓이를 구하는 부분이 필요하기 때문에 외적하는 부분을 area()로 따로 분리한 것 이외는 차이가 없다.

윗껍질, 아랫껍질 분리하기

컨벅스 헐을 구했으면 넓이를 계산하기 위해 윗 껍질과 아래껍질로 분리했다.

컨벡스 헐을 구하는 알고리즘 중에 모노톤 체인 기법을 이용하면 편리하게 분리할 수 있겠지만 그라함 스캔이 익숙해서 컨벡스 헐을 구한 뒤 이를 분리했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void sep(vector<point>& ch, vector<point>& up, vector<point>& down) {
    int l = (int)ch.size();
    up.push_back(ch[l - 1]); down.push_back(ch[l - 1]);

    int i = 0;
    while (ch[i][0] <= ch[i + 1][0]) {
        up.push_back(ch[i++]);
    }
    up.push_back(ch[i]);
    int j = l - 2;
    while (i <= j) {
        down.push_back(ch[j--]);
    }
}

내가 사용하는 컨벡스 헐은 정점들이 시계방향으로 담겨있기 때문에 방향에 유의해서 up과 down 벡터에 $x$좌표가 증가하는 방향으로 좌표들이 저장될 수 있게 했다.

[예제 1]을 sep() 함수까지 실행하면 아래와 같이 윗껍질과 아래껍질이 분리되는 것을 볼 수 있다.

img_3.png

solve 함수 만들기 (1) - 컨벡스 헐과 직선의 교점 구하기

이분 탐색을 돌 때 조건을 어떻게 만족하는지에 따라 lo와 hi를 변경하는데 이를 판별하기위한 solve() 함수가 필요하다.

solve() 함수에서는 $x=mid$에서 왼쪽 구역과 오른쪽 구역을 나누고 이 두 구역의 넓이를 비교한다.

왼쪽 구역과 오른쪽 구역을 나누기 위해서는 컨벡스 헐과 $x=mid$의 교점이 필요하다.

교점이 한 껍질의 두 점 $a(x_1, y_1), b(x_2, y_2)$을 잇는 선분에 생길 때 우리는 교점의 $x$좌표인 $mid$를 알고 있기 때문에 up과 down에서 $x$좌표에 대해 $mid$로 lower_bound를 사용한다면 $b$의 좌표를 구할 수 있다.

$a$점은 $b$점의 바로 이전 점이기 때문에 추가적으로 구할 필요가 없다.

컨벡스 헐은 각 점을 직선으로 연결하기 때문에 선형 보간을 이용해 선분과 직선의 교점$(x, y)$을 찾을 수 있다.

$$ x = mid \quad y = y_1 + t(y_2 - y_1) \quad t=\frac {(mid - x_1)}{(x_2 - x_1)} $$

1
2
3
4
5
6
7
8
9
10
11
12
point intersection(point& a, point& b, double c) {
    double t = (c - a[0]) / (b[0] - a[0]);
    return {c, a[1] + t * (b[1] - a[1])};
}

int solve(vector<point>& up, vector<point>& down, double mid) {
    point m = {mid, 0};
    int ui = lower_bound(up.begin(), up.end(), m) - up.begin();
    int di = lower_bound(down.begin(), down.end(), m) - down.begin();

    point u = intersection(up[ui - 1], up[ui], mid);
    point d = intersection(down[di - 1], down[di], mid);

lower_bound를 통해 윗껍질과 아랫껍질에서 교차하는 선분을 구하고, intersection() 함수에서 선분과 만나는 교점을 구해주었다.

solve 함수 만들기 (2) - 두 영역의 넓이 구하기

영역을 구할 때 2166 - 다각형의 면적 문제처럼 다각형의 이루는 순서대로 배열에 담겨 있으면 쉽게 넓이를 구할 수 있다.

따라서 아래와 같이 시계 반대 방향 순서로 점들을 점들을 담아주었다.

img_4.png

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<point> p1;
p1.reserve(up.size() + down.size());
for (int i = 0; i < di; i++) p1.push_back(down[i]);
p1.push_back(d);
p1.push_back(u);
for (int i = ui - 1; i > 0; i--) p1.push_back(up[i]);

vector<point> p2;
p2.reserve(up.size() + down.size());
p2.push_back(d);
for (int i = di; i < down.size(); i++) p2.push_back(down[i]);
for (int i = up.size() - 2; i >= ui; i--) p2.push_back(up[i]);
p2.push_back(u);

만약 담는 과정에서 교점이 컨벡스 헐을 구성하는 점을 지나간다면 같은 점이 두 번 배열에 담길 수도 있지만, CCW를 계산할 때 0이 나와 상관이 없다.

1
2
3
4
5
6
7
8
9
10
11
12
13
double area(vector<point>& a) {
    double sum = 0;
    for (int i = 2; i < (int)a.size(); i++) {
        sum += abs(area(a[0], a[i - 1], a[i]));
    }
    return sum;
}

int solve(vector<point>& up, vector<point>& down, double mid) {
    // 생략
    double left = area(p1), right = area(p2);
    return left < right;
}

area() 함수를 통해 p1배열과 p2 배열의 넓이를 각각 구해주고 왼쪽 부분과 오른쪽 부분 넓이를 비교한 결과를 반환했다.

이분 탐색 만들기

lo는 $x_{min}$, hi는 $x_{max}$로 설정하고 (lo + 1e-5 < hi)를 만족할 때까지 이분 탐색을 반복했다.

solve() 함수가 true면 왼쪽 구역의 넓이가 더 작으므로 lo = mid로 설정하고,

false면 오른쪽 구역의 넓이가 더 작으므로 hi = mid로 설정했다.

반복이 끝났으면 lo, hi의 차이가 $10^{-5}$보다 작아 lo, hi중 둘 중 아무거나 출력해도 문제의 출력조건 절대/상대 오차가 $10^{-3}$ 이하를 만족해서, lo를 출력했다.

1
2
3
4
5
6
7
8
9
double lo = up[0][0], hi = up[up.size() - 1][0];
while (lo+1e-5<hi) {
    double mid = (lo + hi) / 2;
    if (solve(up, down, mid)) lo = mid;
    else hi = mid;
}
cout << fixed;
cout.precision(4);
cout << lo;

코드

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;

typedef array<double, 2> point;

double area(point& a, point& b, point& c) {
    return (a[0] * b[1] + b[0] * c[1] + c[0] * a[1] - (b[0] * a[1] + c[0] * b[1] + a[0] * c[1])) / 2;
}

int CCW(point& a, point& b, point& c) {
    double ans = area(a, b, c);
    if (ans > 0) return 1;
    if (ans < 0) return -1;
    return 0;
}

int dist(point& a, point& b) {
    int dx = b[0] - a[0], dy = b[1] - a[1];
    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> ch(st.size());
    for (auto& p : ch) p = v[st.top()], st.pop();
    return ch;
}

void sep(vector<point>& ch, vector<point>& up, vector<point>& down) {
    int l = (int)ch.size();
    up.push_back(ch[l - 1]); down.push_back(ch[l - 1]);

    int i = 0;
    while (ch[i][0] <= ch[i + 1][0]) {
        up.push_back(ch[i++]);
    }
    up.push_back(ch[i]);
    int j = l - 2;
    while (i <= j) {
        down.push_back(ch[j--]);
    }
}

point intersection(point& a, point& b, double c) {
    double t = (c - a[0]) / (b[0] - a[0]);
    return {c, a[1] + t * (b[1] - a[1])};
}

double area(vector<point>& a) {
    double sum = 0;
    for (int i = 2; i < (int)a.size(); i++) {
        sum += abs(area(a[0], a[i - 1], a[i]));
    }
    return sum;
}

int solve(vector<point>& up, vector<point>& down, double mid) {
    point m = {mid, 0};
    int ui = lower_bound(up.begin(), up.end(), m) - up.begin();
    int di = lower_bound(down.begin(), down.end(), m) - down.begin();

    point u = intersection(up[ui - 1], up[ui], mid);
    point d = intersection(down[di - 1], down[di], mid);

    vector<point> p1;
    p1.reserve(up.size() + down.size());
    for (int i = 0; i < di; i++) p1.push_back(down[i]);
    p1.push_back(d);
    p1.push_back(u);
    for (int i = ui - 1; i > 0; i--) p1.push_back(up[i]);

    vector<point> p2;
    p2.reserve(up.size() + down.size());
    p2.push_back(d);
    for (int i = di; i < down.size(); i++) p2.push_back(down[i]);
    for (int i = up.size() - 2; i >= ui; i--) p2.push_back(up[i]);
    p2.push_back(u);

    double left = area(p1), right = area(p2);

    return left < right;
}

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

    int N; cin >> N;
    vector<point> v(N);
    for (auto& [x, y] : v) cin >> x >> y;

    vector<point> ch(convexhull(v));

    vector<point> up, down;
    sep(ch, up, down);

    double lo = up[0][0], hi = up[up.size() - 1][0];
    while (lo+1e-5<hi) {
        double mid = (lo + hi) / 2;
        if (solve(up, down, mid)) lo = mid;
        else hi = mid;
    }
    cout << fixed;
    cout.precision(4);
    cout << lo;
}

후기

img_5.png

문제를 어떻게 풀어야하는지 아이디어는 쉽지만 구현이 복잡하고, 실수하기 쉬운 문제였다.

부동 소숫점으로 이분 탐색을 도는 경우가 처음이라 종료 조건을 잘못 세우는 바람에 3번 틀렸다.