AtCoder Beginner Contest 418 E

https://atcoder.jp/contests/abc418/tasks/abc418_e

2点の組み合わせを線分として、全ての線分を方向で分類します。そうすると、同じ類の中の線分の2つの組み合わせが台形になります。ただし、同じ直線内の線分は除きます。
平行四辺形だと二重にカウントしていることになるので、平行四辺形を数えてその分を取り除きます。線分が同じベクトルだと平行四辺形になります。ただし、同じ直線内の線分は除きます。

// XNOR Operation
#![allow(non_snake_case)]

use std::collections::{HashMap, BTreeSet};
use std::cmp::min;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn gcd<T>(mut a: T, mut b: T) -> T
where
    T: std::ops::Rem<Output = T> + std::cmp::PartialEq + std::convert::From<u8> + Copy,
{
    while b != T::from(0u8) {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}


//////////////////// process ////////////////////

type Point = (i32, i32);
type Comb = (Point, Point);
type Slope = (i32, i32);

fn read_point() -> Point {
    let v: Vec<i32> = read_vec();
    let (X, Y) = (v[0], v[1]);
    (X, Y)
}

fn read_input() -> Vec<Point> {
    let N: usize = read();
    let points: Vec<Point> = (0..N).map(|_| read_point()).collect();
    points
}

fn calc_slope(pt1: Point, pt2: Point) -> Slope {
    let dx = pt2.0 - pt1.0;
    let dy = pt2.1 - pt1.1;
    if dx == 0 {
        (0, 1)
    }
    else if dy == 0 {
        (1, 0)
    }
    else {
        let d = gcd(dx.abs(), dy.abs());
        if dx > 0 {
            (dx / d, dy / d)
        }
        else {
            (-dx / d, -dy / d)
        }
    }
}

fn calc_vector(pt1: Point, pt2: Point) -> Point {
    let dx = pt2.0 - pt1.0;
    let dy = pt2.1 - pt1.1;
    if dx == 0 {
        (0, dy.abs())
    }
    else if dy == 0 {
        (dx.abs(), 0)
    }
    else {
        if dx > 0 {
            (dx, dy)
        }
        else {
            (-dx, -dy)
        }
    }
}

// dirに沿って、xが0以上でなるべく小さくなるようにする
fn mod_point(point: Point, dir: Point) -> Point {
    if dir.0 == 0 {
        let r = point.1.rem_euclid(dir.1);  // dir.1 > 0のはず
        (point.0, r)
    }
    else {
        let r = point.0.rem_euclid(dir.0);
        let q = (point.0 - r) / dir.0;
        (r, point.1 - q * dir.1)
    }
}

fn F_each(combs: &Vec<Comb>, dir: Point) -> usize {
    let set_points: BTreeSet<Point> = combs.iter().
                                        flat_map(|t| vec![t.0, t.1]).
                                        collect();
    let points: Vec<Point> = set_points.into_iter().collect();
    let mut groups: HashMap<Point, Vec<Point>> = HashMap::new();
    for &pt in points.iter() {
        let pt0 = mod_point(pt, dir);
        let e = groups.entry(pt0).or_insert(vec![]);
        (*e).push(pt)
    }
    
    let mut counter: usize = 0;
    let n = combs.len();
    for (_, vs) in groups {
        let m = vs.len() * (vs.len() - 1) / 2;
        counter += m * (n - m)
    }
    counter / 2
}

fn G_each(pts: &Vec<Point>, dir: Point) -> usize {
    // 同じ線上にある2点の組合せはいくつあるか
    let d = gcd(dir.0.abs(), dir.1.abs());
    let dir0 = (dir.0 / d, dir.1 / d);
    let mut counter: HashMap<Point, usize> = HashMap::new();
    for &pt in pts.iter() {
        let pt0 = mod_point(pt, dir0);
        let e = counter.entry(pt0).or_insert(0);
        *e += 1
    }
    
    let n = pts.len();
    let mut s: usize = 0;
    for (_, m) in counter {
        s += m * (n - m)
    }
    s / 2
}

fn F(points: Vec<Point>) -> usize {
    // 平行な点の組合せを集める
    let N = points.len();
    let mut dic_combs: HashMap<Slope, Vec<Comb>> = HashMap::new();
    for i in 0..N-1 {
        for j in i+1..N {
            let slope = calc_slope(points[i], points[j]);
            let e = dic_combs.entry(slope).or_insert(vec![]);
            (*e).push((points[i], points[j]))
        }
    }
    
    let mut counter: usize = 0;
    for (slope, combs) in dic_combs {
        counter += F_each(&combs, slope)
    }
    
    // 平行四辺形を二重にカウントしているので除かないといけない
    // 同じベクトルを集める
    let mut dic_vectors: HashMap<Point, Vec<Point>> = HashMap::new();
    for i in 0..N-1 {
        for j in i+1..N {
            let v = calc_vector(points[i], points[j]);
            let e = dic_vectors.entry(v).or_insert(vec![]);
            (*e).push(min(points[i], points[j]))
        }
    }
    
    let mut counter_para: usize = 0;
    for (dir, pts) in dic_vectors {
        counter_para += G_each(&pts, dir)
    }
    
    counter - counter_para / 2
}

fn main() {
    let points = read_input();
    println!("{}", F(points))
}