Namaran

Code daily. Without assist.

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つずつ進める書き方もできます。