2026-10-01
polygon.cpp
struct Point {
long long x, y;
};
long long doubled_area(std::span<const Point> ps) {
}
境界に沿った順に頂点を並べた多角形を受け取り、その面積の2倍を返す doubled_area を書いてください。頂点の座標は整数で、並びは時計回りでも反時計回りでもかまいません。辺どうしは交わりません。頂点が2つ以下のときは 0 を返します。
入力例 1
doubled_area(std::vector<Point>{{0, 0}, {2, 0}, {2, 2}, {0, 2}})
出力例 1
8
入力例 2
doubled_area(std::vector<Point>{{0, 0}, {0, 3}, {1, 0}})
出力例 2
3
入力例 3
doubled_area(std::vector<Point>{{5, 5}})
出力例 3
0
Reference
long long doubled_area(std::span<const Point> ps) {
long long s = 0;
for (std::size_t i = 0; i < ps.size(); ++i) {
const Point& a = ps[i];
const Point& b = ps[(i + 1) % ps.size()];
s += a.x * b.y - b.x * a.y;
}
return s < 0 ? -s : s;
}
隣り合う2頂点 a、b ごとに a.x * b.y - b.x * a.y を足すと、和の絶対値が面積の2倍になります。和の符号は頂点の向きで決まり、反時計回りなら正、時計回りなら負です。例2の三角形は時計回りで、和は -3 になるので、最後に絶対値を取ります。格子点の多角形の面積は 0.5 刻みなので、2倍なら整数のまま返せます。
忘れやすいのは、最後の頂点から最初の頂点へ戻る組です。b の添字を (i + 1) % ps.size() にすると、i が最後の頂点を指すときに b が ps[0] になり、多角形が閉じます。この項を落とした和は、多角形を平行移動しただけで値が変わります。
頂点が2つ以下の場合を別に扱う必要はありません。1つなら a と b が同じ点で項が 0、2つなら往復の2項が打ち消し合い、空ならループが一度も回らないので、どれも 0 が返ります。
掲載したのは参考実装で、唯一の正解ではありません。空のときに先に 0 を返しておけば、直前の頂点を ps.back() で初期化した変数に持ち、範囲 for で1つずつ進める書き方もできます。