백준 10321 - 요새 건설#

핵심 아이디어#

껍질에 있는 점들을 대상으로 임의의 대각선에 대해서 해당 대각선에서 가장 먼 점 2개를 고르면 해당 대각선으로 만들 수 있는 가장 큰 영역이다. 이때 먼점 2개는 대각선을 기준으로 서로 다른 영역에 있음을 가정한다.

풀이#

1. Graham Scan을 이용해서 Convex Hull을 구한다. 이때 Hull에 있는 점들은 반시계 방향 순서대로 정렬되어 있다.
2. Hull(껍질)에 있는 점들에 대해서 임의의 2개의 점을 고르고 2점을 이어서 만든 대각선에 대해 가장 먼 점 2개를 고른다. (이때 먼 점 2개는 대각선을 기준으로 서로 다른 영역에 있음을 의미함.)
   • 임의의 2개 점을 i, j라 하자. i를 고정시키고 j를 반시계 방향으로 증가시키면서 이동한다고 가정하자.
   • 각 영역의 가장 먼 점을 a, b라 하자.
   • j가 반시계 방향으로 이동하면 a와 b 모두 반 시계 방향으로 이동할 수 밖에 없다. 따라서 a,b의 이동횟수는 한 개의 i에 대해서 n번 씩이다.
   • 따라서 $O(n^2)$ 만에 모든 대각선들에 대한 영역을 검사할 수 있다.

코드#

1#include <bits/stdc++.h>
2
3#define endl "\n"
4#define all(v) (v).begin(), (v).end()
5#define all1(v) (v).begin()+1, (v).end()
6#define For(i, a, b) for(int i=(a); i<(b); i++)
7#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
8#define Bor(i, a, b) for(int i=(a)-1; i>=(b); i--)
9#define BOR(i, a, b) for(int i=(a); i>=(b); i--)
10#define ft first
11#define sd second
12
13using namespace std;
14using ll = long long;
15using lll = __int128_t;
16using ulll = __uint128_t;
17using ull = unsigned long long;
18using ld = long double;
19using pii = pair<int, int>;
20using pll = pair<ll, ll>;
21using ti3 = tuple<int, int, int>;
22using tl3 = tuple<ll, ll, ll>;
23
24template<typename T> using ve = vector<T>;
25template<typename T> using vve = vector<vector<T>>;
26
27template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
28template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
29
30const int INF = 987654321;
31const int INF0 = numeric_limits<int>::max();
32const ll LNF = 987654321987654321;
33const ll LNF0 = numeric_limits<ll>::max();
34
35struct Point {
36    ll x, y;
37
38    Point() {}
39    Point(ll _x, ll _y) : x(_x), y(_y) {}
40    ll cross(Point other) {
41        return x*other.y - y*other.x;
42    }
43    ll crossSign(Point other) {
44        ll res = this->cross(other);
45        if(res > 0) return 1;
46        else if(res < 0) return -1;
47        return 0;
48    }
49    ll dist(Point other) {
50        return pow(x-other.x,2) + pow(y-other.y,2);
51    }
52    Point operator-(Point other) const {
53        return Point(x-other.x, y-other.y);
54    }
55    bool operator==(Point other) const {
56        return x == other.x && y == other.y;
57    }
58    bool operator<(Point other) const {
59        if(x == other.x) return y < other.y;
60        return x < other.x;
61    }
62    void print() {
63        cout << x << ' ' << y << ' ';
64    }
65};
66
67Point reference;
68
69vector<Point> Graham_Scan(vector<Point> &points) {
70    sort(all(points)); points.erase(unique(all(points)), points.end());
71    reference = points[0];
72    auto cmp = [&](Point a, Point b) {
73        ll res = (a - reference).cross(b - reference);
74        if(res != 0) return res > 0;
75        return reference.dist(a) < reference.dist(b);
76    };
77    sort(points.begin()+1, points.end(), cmp);
78
79    vector<Point> convex;
80    for(Point p3 : points) {
81        while(convex.size() >= 2) {
82            Point p2 = convex.back();
83            Point p1 = convex[convex.size() - 2];
84            ll ccw = (p2-p1).cross(p3-p2);
85            if(ccw > 0) break;
86            convex.pop_back();
87        }
88        convex.emplace_back(p3);
89    }
90    return convex;
91}
92
93ll triangle(Point &p1, Point &p2, Point &p3) {
94    ll res = abs(p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p2.x*p1.y - p3.x*p2.y - p1.x*p3.y);
95//    if(res % 2 == 0) return (ld)((ll)(res/2));
96//    return (ld)((ll)(res/2) + 0.5);
97    return res;
98}
99
100int n;
101ve<Point> v;
102
103void solve() {
104    cin >> n;
105    ve<Point>tmp(n);
106    For(i,0,n) cin >> tmp[i].x >> tmp[i].y;
107    v = Graham_Scan(tmp);
108
109//    for(auto x:v) {
110//        x.print();
111//        cout << endl;
112//    }
113
114    n = v.size();
115   if(n == 3) {
116        ll res = triangle(v[0], v[1], v[2]);
117        if(res%2 == 0) cout << res/2 << endl;
118        else cout << res/2 << ".5\n";
119        return;
120    }
121
122
123    ll ret = 0;
124    For(i,0,n) {
125        int a=(i+1)%n, b=(i+3)%n;
126        For(j, i+2, n) {
127            while(true) {
128                int na = (a+1)%n;
129                if(na == j) break;
130                if(triangle(v[i], v[j], v[a]) < triangle(v[i], v[j], v[na])) a = na;
131                else break;
132            }
133            while(true) {
134                int nb = (b+1)%n;
135                if(nb == i) break;
136                if(triangle(v[i],v[j],v[b]) < triangle(v[i],v[j],v[nb])) b = nb;
137                else break;
138            }
139            ckmax(ret, triangle(v[i],v[j],v[a]) + triangle(v[i],v[j],v[b]));
140        }
141
142    }
143
144    if(ret%2 == 0) cout << ret/2 << endl;
145    else cout << ret/2 << ".5\n";
146}
147
148int main(void) {
149    ios_base::sync_with_stdio(false);
150    cin.tie(nullptr);
151    cout.tie(nullptr);
152
153    cout << fixed << setprecision(1);
154
155    int TC=1;
156    cin >> TC;
157    FOR(tc, 1, TC) {
158//        cout << "Case #" << tc << ": ";
159        solve();
160    }
161
162
163    return 0;
164}

오답노트#

1. 처음에는 한 점에 대해서 가장 먼 점을 구하면 해당 대각선으로 만든 영역 중 가장 큰 것이 해당 점을 기주으로 했을 때 최선이라 가정했으나, 이 가정을 증명할 수 없어서 틀렸다.
   모든 대각선에 대해서 검사하고 a,b가 n번 씩 밖에 움직일 필요가 없음을 이용해야 했다.
2. 위 풀이대로 구현하였는데 틀렸습니다가 나왔다. ret을 -1로 초기화했는데, ret이 한번도 업데이트되지 않는 경우가 존재한 모양이다. (심지어 $n < 3$ 일 때 0을 반환해주도록 했는데, 그 외의 경우도 있는 듯 하다.)

참고#

• https://justicehui.github.io/icpc/2019/02/04/BOJ10321/