2026-11-11
parabola.rs
fn cross(o: (i32, i32), a: (i32, i32), b: (i32, i32)) -> i32 {
(a.0 - o.0) * (b.1 - o.1) - (a.1 - o.1) * (b.0 - o.0)
}
fn main() {
let p: Vec<(i32, i32)> = (-4..=4).map(|x| (x, x * x)).collect();
let mut left = 0;
for i in 0..p.len() {
for j in i + 1..p.len() {
for k in j + 1..p.len() {
if cross(p[i], p[j], p[k]) > 0 {
left += 1;
}
}
}
}
println!("{left}");
}
これは何を出力するでしょうか?
Answer
Output
84
cross(o, a, b) は、o から a へ進み、そこから b へ向かうときに左へ曲がるなら正、右へ曲がるなら負、一直線なら0になる値です。p は x = −4 から 4 までの9点 (x, x²) を x の小さい順に並べたもので、三重ループは i < j < k のすべての組、つまり9点から3点を選ぶ 9C3 = 84 通りを調べます。
84通りを1つずつ計算しなくても、この点の並びなら式から符号が決まります。x 座標が x1, x2, x3 の3点を入れると、値は (x2 − x1)(x3² − x1²) − (x2² − x1²)(x3 − x1) です。(x2 − x1)(x3 − x1) でくくると、残りは (x3 + x1) − (x2 + x1) = x3 − x2 なので、全体は (x2 − x1)(x3 − x1)(x3 − x2) になります。i < j < k なら x1 < x2 < x3 で、3つの差はどれも正です。したがってどの組も正になり、left は 84 です。
(−2, 4), (0, 0), (2, 4) のように y 軸に対して左右対称な組を見ると、向きが打ち消し合いそうに思えます。実際には、この組も x の小さい順に回ると左に曲がり、値は 2 × 4 × 2 = 16 です。放物線 y = x² は下に凸な曲線なので、その上の点を x の順にたどると、どの3点を取っても左へ曲がります。一直線に並ぶ3点も無いので、0になる組もありません。