Namaran

Code daily. Without assist.

2026-11-11

triangle.rs

type Point = (i64, i64);

fn cross(o: Point, a: Point, b: Point) -> i64 {
    (a.0 - o.0) * (b.1 - o.1) - (a.1 - o.1) * (b.0 - o.0)
}

fn contains(tri: [Point; 3], p: Point) -> bool {
}

cross(o, a, b) は、o から a へ進み、そこから b へ向かうときに左へ曲がるなら正、右へ曲がるなら負、一直線なら0を返します。これを使い、点 p が三角形 tri の内側か辺の上にあれば true、外側なら false を返す contains を書いてください。tri の3頂点は一直線に並ばず、左回りと右回りのどちらの順でも来ます。

入力例 1

contains([(0, 0), (4, 0), (0, 4)], (1, 1))

出力例 1

true

入力例 2

contains([(0, 0), (4, 0), (0, 4)], (3, 3))

出力例 2

false

入力例 3

contains([(0, 0), (0, 4), (4, 0)], (2, 2))

出力例 3

true
Reference

Reference

fn contains(tri: [Point; 3], p: Point) -> bool {
    let [a, b, c] = tri;
    let s = [cross(a, b, p), cross(b, c, p), cross(c, a, p)];
    s.iter().all(|&v| v >= 0) || s.iter().all(|&v| v <= 0)
}

三角形の辺を a → b → c → a の順にたどると、内側の点はどの辺から見ても同じ側にあります。そこで3本の辺それぞれについて cross を求め、3つの符号がそろっているかを調べます。頂点が左回りなら内側の点は3つとも正、右回りなら3つとも負になるので、「すべて0以上」か「すべて0以下」のどちらかが成り立てば内側です。辺の上の点では、その辺の値が0になり、0は両方の条件に入るので true になります。これは参考実装で、唯一の正解ではありません。

入力例1の三角形は左回りで、(1, 1) に対する3つの値は 4, 8, 4 とすべて正です。(3, 3) では辺 (4, 0) → (0, 4) に対する値だけが −8 になり、符号がそろわないので false を返します。入力例3は頂点が右回りで、(2, 2) は辺 (0, 4) → (4, 0) の上にあります。値は −8, 0, −8 で、すべて0以下なので true です。let [a, b, c] = tri; は配列のパターンで3頂点に名前を付けており、要素数が型で3に決まっているので、このパターンは必ず一致します。