2026-10-01
shoelace.cpp
#include <cstdlib>
#include <iostream>
#include <ranges>
#include <vector>
struct P { int x, y; };
int area(const std::vector<P>& ps) {
int s = 0;
for (auto [a, b] : ps | std::views::pairwise)
s += a.x * b.y - b.x * a.y;
return std::abs(s) / 2;
}
int main() {
std::cout << area({{0, 0}, {2, 0}, {2, 2}, {0, 2}}) << ' '
<< area({{1, 1}, {3, 1}, {3, 3}, {1, 3}}) << '\n';
}
これは何を出力するでしょうか?
Answer
4 5 です。
靴紐公式は、隣り合う2頂点 a、b ごとに a.x * b.y - b.x * a.y を足し、その和の絶対値を面積の2倍とします。ただし和には、最後の頂点から最初の頂点へ戻る組も含めます。std::views::pairwise が作る組は (ps[0], ps[1])、(ps[1], ps[2])、(ps[2], ps[3]) の3つだけで、多角形を閉じる (ps[3], ps[0]) はありません。
それでも1つ目の正方形は正しく求まります。抜けた組は (0, 2) と (0, 0) で、原点を含む組の項は 0 * 0 - 0 * 2 のように必ず 0 になるからです。3組の和 0 + 4 + 4 = 8 は本来の和と一致し、4 が出力されます。
2つ目は同じ正方形を (1, 1) だけ動かしたもので、本当の面積は 4 のままです。しかし原点を含む頂点がなくなったので、抜けた組 (1, 3) と (1, 1) の項 1 * 1 - 1 * 3 = -2 は 0 ではありません。3組の項は -2、6、6 で、和の 10 を2で割った 5 が出力されます。
pairwise が最後と最初も組にすると読んでも、組の欠けに気付いたうえで平行移動では面積が変わらないと考えても、答えは 4 4 になります。和が平行移動で変わらないのは、多角形を閉じるまで足したときだけです1。
- 各項は、原点と2頂点がなす三角形の符号付き面積の2倍です。多角形が閉じていれば、原点をどこに置いても、多角形の外にはみ出した三角形どうしが打ち消し合います。閉じていない和では、その打ち消し合う相手が1つ欠けます。