けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 250 F - One Fourth (黄色, 600 点)

くしらっちょ君と一緒に解いた! 実装が辛い。

問題概要

頂点数が  N である凸多角形が与えられる。この凸多角形の面積を  S とする。

今、凸多角形の隣接しない 2 頂点を結ぶ直線によって凸多角形を 2 つの多角形に分ける。そして、2 つの多角形うちの 1 つをとって、その面積を  b とする。

 8 \times |b - \frac{S}{4}| の値の最小値を求めよ。

制約

  •  4 \le N \le 10^{5}
  • 各頂点の座標の絶対値は  4 \times 10^{8} 以下

考えたこと

まず、この問題は C++ の double 型を用いると精度が足りないことの注意しよう。なぜなら、double 型は有効精度が 15 桁程度までしかない。しかし今回は、その制約から、 16 \times 10^{16} くらいの精度が必要だ。よって、long long 型を用いることにしよう。

解法自体は、しゃくとり法が自然に思い浮かぶ。

頂点  i, i+1, \dots, j (%N をとるものとする) を結ぶ多角形の面積を  f(i, j) と表すとき、1 点  i を進めるたびに、もう 1 点  j f(i, j) \gt \frac{S}{4} となるまで動かしていくのを繰り返すのだ。

その都度  f(i, j) の更新を  O(1) でできるので、全体の計算量も  O(N) となる。

コード

#include <bits/stdc++.h>
using namespace std;

using pint = pair<int, int>;
using pll = pair<long long, long long>;

int main() {
    int N;
    cin >> N;
    vector<long long> x(N), y(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
    
    auto area = [&](int i, int j, int k) -> long long {
        long long dx1 = x[j] - x[i], dy1 = y[j] - y[i];
        long long dx2 = x[k] - x[i], dy2 = y[k] - y[i];
        long long res = abs(dx1 * dy2 - dx2 * dy1);
        return res;
    };
    
    long long a = 0;
    for (int i = 1; i < N-1; ++i) a += area(0, i, i+1);
    
    long long res = a;
    long long cur = 0;
    int i = 0, j = 1;
    for (i = 0; i < N; ++i) {
        res = min(res, abs(cur - a));
        while (cur <= a) {
            cur += area(i, j, (j+1) % N) * 4;
            res = min(res, abs(cur - a));
            j = (j+1) % N;
        }
        
        // 面積を減らす
        cur -= area(j, i, (i+1)%N) * 4;
    }
    cout << res << endl;
}