취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27947번 문제인 가지 밭 게임이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/27947

새로운 말뚝을 하나 추가하면 가장 큰 다각형의 넓이는 커지거나 그대로일 수는 있지만 작아질 수는 없다는 점을 관찰하자. 기존 말뚝으로 만들 수 있는 다각형을 여전히 다 만들 수 있기 때문이다.

따라서 게임이 진행되면 만들어질 수 있는 가장 큰 다각형의 넓이는 단조증가하므로 게임이 몇 번째 차례까지 진행되어야 최대 넓이가 \(A\) 이상이 되는지는 이분탐색으로 구할 수 있다.

주어지는 점을 꼭짓점으로 하여 구성할 수 있는 가장 넓이가 큰 다각형은 주어진 점의 볼록 껍질(convex hull)과 같으므로 볼록 껍질을 구하는 다양한 알고리즘(글쓴이는 Andrew's algorithm을 구현하였다.)과 다각형의 넓이를 구하는 식인 사선 공식(shoelace formula)을 활용해 어렵지 않게 구현할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

ll CCW(pll &p1, pll &p2, pll &p3) {
    return p1.first * p2.second + p2.first * p3.second + p3.first * p1.second - p1.first * p3.second - p2.first * p1.second - p3.first * p2.second;
}

ll N, A, L, R;
vector<pair<pll, int>> P;
vector<pll> uhull, lhull;

ll func(ll K) {
    uhull.clear(), lhull.clear();
    for (auto &p:P) {
        if (p.second > K) continue;
        while (uhull.size() > 1 && CCW(uhull[uhull.size() - 2], uhull.back(), p.first) >= 0) uhull.pop_back();
        uhull.emplace_back(p.first);
    }
    for (auto &p:P) {
        if (p.second > K) continue;
        while (lhull.size() > 1 && CCW(lhull[lhull.size() - 2], lhull.back(), p.first) <= 0) lhull.pop_back();
        lhull.emplace_back(p.first);
    }
    lhull.pop_back();
    while (!lhull.empty()) {
        uhull.emplace_back(lhull.back());
        lhull.pop_back();
    }
    ll usize = uhull.size(), ret = 0;
    for (int i = 0; i + 1 < usize; i++) ret += uhull[i].first * uhull[i + 1].second - uhull[i].second * uhull[i + 1].first;
    return abs(ret);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> A; A *= 2;
    P.reserve(N + 3);
    uhull.reserve(N + 4), lhull.reserve(N + 4);
    for (int i = -2; i <= N; i++) {
        ll x, y; cin >> x >> y;
        P.emplace_back(make_pair(make_pair(x, y), i));
    }
    
    sort(P.begin(), P.end());
    if (func(N) < A) {
        cout << "draw";
        return 0;
    }
    
    L = 1, R = N;
    while (L < R) {
        ll mid = (L + R) / 2;
        if (func(mid) >= A) R = mid;
        else L = mid + 1;
    }
    
    if (L & 1) cout << "wapas";
    else cout << "wider";
}