くしらっちょ君と一緒に解いた! 実装が辛い。
問題概要
頂点数が である凸多角形が与えられる。この凸多角形の面積を とする。
今、凸多角形の隣接しない 2 頂点を結ぶ直線によって凸多角形を 2 つの多角形に分ける。そして、2 つの多角形うちの 1 つをとって、その面積を とする。
の値の最小値を求めよ。
制約
- 各頂点の座標の絶対値は 以下
考えたこと
まず、この問題は C++ の double
型を用いると精度が足りないことの注意しよう。なぜなら、double
型は有効精度が 15 桁程度までしかない。しかし今回は、その制約から、 くらいの精度が必要だ。よって、long long
型を用いることにしよう。
解法自体は、しゃくとり法が自然に思い浮かぶ。
頂点 (%N をとるものとする) を結ぶ多角形の面積を と表すとき、1 点 を進めるたびに、もう 1 点 を となるまで動かしていくのを繰り返すのだ。
その都度 の更新を でできるので、全体の計算量も となる。
コード
#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; }