2026-11-04
polygon_area.rs
fn area(p: &[(i64, i64)]) -> f64 {
}
頂点の座標 p を、多角形の周に沿って順に並べたスライスを受け取り、その多角形の面積を返す area を書いてください。多角形の辺どうしは交わらず、頂点は左回りに並んでいても右回りに並んでいてもかまいません。最後の頂点と最初の頂点の間にも辺があり、最初の頂点を末尾にもう一度置くことはしません。頂点が3個未満なら 0.0 を返します。
入力例 1
area(&[(1, 1), (5, 1), (5, 4)])
出力例 1
6.0
入力例 2
area(&[(0, 0), (0, 2), (2, 2), (2, 0)])
出力例 2
4.0
入力例 3
area(&[(0, 0), (1, 0), (0, 1)])
出力例 3
0.5
Reference
fn area(p: &[(i64, i64)]) -> f64 {
let n = p.len();
let twice: i64 = (0..n)
.map(|i| {
let (a, b) = (p[i], p[(i + 1) % n]);
a.0 * b.1 - b.0 * a.1
})
.sum();
twice.abs() as f64 / 2.0
}
隣り合う2頂点 a と b について a.0 * b.1 - b.0 * a.1 を計算し、すべての辺について足し合わせると、多角形の面積の2倍になります。1つの項は、原点と a と b を頂点とする三角形の面積の2倍に、左回りなら正、右回りなら負の符号を付けたものです。辺ごとの三角形を足し合わせると、多角形の外にはみ出した部分は符号が逆の項と打ち消し合います。1
和には頂点の並びの向きで符号が付くので、abs で絶対値をとってから2で割ります。入力例 2 は右回りの並びで、和は -8 です。最後の頂点と最初の頂点の組は、添字 (i + 1) % n で作ります。i が最後の n - 1 のとき、相手の添字が 0 に戻ります。この組を落とすと、閉じていない折れ線の分しか足されず、入力例 1 は 5.5 になってしまいます。
座標が整数なので、和は i64 のまま正確に求め、最後に1回だけ f64 にしています。面積の2倍は必ず整数で、2で割った結果は整数か、端数が 0.5 のどちらかです。頂点が0個なら和は空で 0 に、1個なら唯一の項が a.0 * a.1 - a.0 * a.1 = 0 に、2個なら往復の2項が打ち消し合って 0 になるので、3個未満の場合を別に書く必要はありません。掲載したのは参考実装で、唯一の正解ではありません。p.iter().zip(p.iter().cycle().skip(1)) で、隣り合う組を最後の頂点から最初の頂点への組まで作ることもできます。
- この式は靴紐公式(くつひもこうしき、shoelace formula)と呼ばれます。x 座標と y 座標を2列に並べ、斜めに掛けて足し引きする様子が、靴紐を交差させて通す形に似ていることからの名前です。