Trapezium の解説

「どの 3 点も同一直線上にない」ので、1 本の直線上に乗る点は高々 2 点です。 したがって、2 点組 (i,j) を結ぶ直線を考えると、同じ直線が複数回現れることはありません。

ここで、全ての点対をその直線の傾きごとにグループ分けします。 同じグループに属する 2 本の線分は平行です。

ある傾きグループから 2 本の線分を選ぶことを考えます。 「3 点が同一直線上にない」ことから、それらは異なる 2 本の平行な直線上にある 4 点を与えます。 この 4 点を結ぶと、1 組の対辺が平行な四角形、つまり台形になります。 よって、各グループに含まれる線分数をmとすると、そのグループから作れる台形候補の数は$\binom{n}{2}$個です。

ただし、この数え方では平行四辺形を 2 回数えています。 実際、平行四辺形は 2 組の対辺がともに平行なので、2 つの傾きグループそれぞれで 1 回ずつ数えられます。

そこで平行四辺形の個数を求めて引きます。 四角形が平行四辺形であることと、「1 組の対辺が平行かつ長さが等しい」ことは同値です。 したがって、各傾きグループ内で長さが等しい線分の組を数えれば、それらは平行四辺形を与えます。

ただし 1 つの平行四辺形は 2 つの傾きグループで数えられるため、平行四辺形の総数はこの個数を 2 で割ったものです。 以上より、答えは

$$\sum_{\text{傾きグループ}} \binom{m}{2} - \frac{1}{2} \sum_{\text{傾きグループ}} \sum_{\text{長さ } \ell} \binom{c_\ell}{2}$$

となります。

実装は有理数ライブラリを用いて楽しています。

https://github.com/k-ohnuma/k-ohnuma-procon-lib/blob/main/src/math/fraction.rs

fn main() {
    input! {
        n: usize,
        xy: [(i128, i128); n]
    }
    let mut map = FxHashMap::default();
    let f = |idx1: usize, idx2: usize| {
        let (x1, y1) = xy[idx1];
        let (x2, y2) = xy[idx2];
        let f = Frac::new(y2 - y1, x2 - x1);
        if f.is_inf() {
            Frac::pinf()
        } else {
            f
        }
    };
    for i in 0..n {
        for j in i + 1..n {
            let kata = f(i, j);
            map.entry(kata).or_insert(Vec::new()).push((i, j));
        }
    }
    let mut ans = {
        let mut ans = 0;
        for p in map.iter() {
            let ln = p.1.len();
            if ln <= 1 {
                continue;
            }
            ans += ln * (ln - 1) / 2;
        }
        ans
    };

    let f2 = |i: usize, j: usize| {
        let (x1, y1) = xy[i];
        let (x2, y2) = xy[j];
        x2.abs_diff(x1).pow(2) + y2.abs_diff(y1).pow(2)
    };
    let mut cur = 0;
    for p in map.iter() {
        let mut map = HashMap::new();
        for &(i, j) in p.1.iter() {
            map.entry(f2(i, j)).and_modify(|e| *e += 1).or_insert(1usize);
        }
        for (_, &count) in map.iter() {
            if count <= 1 {
                continue;
            }
            cur += count * (count - 1) / 2;
        }
    }

    println!("{}", ans - cur / 2);
}