Count number of trapezoids ii

impl Solution {
  pub fn count_trapezoids(points: Vec<Vec<i32>>) -> i32 {
    // Strategy:
    //   answer = (quadruples with >=1 parallel pair)
    //          = sum_over_slopes [ pairs_of_distinct_parallel_lines(slope) ] - parallelograms
    //
    // For each slope s, group points by line. A line is uniquely identified by
    // (normalized_slope, intercept) where intercept = ndy*x - ndx*y.
    // For each slope, the count of valid "one parallel pair" quadruples involving
    // two DISTINCT parallel lines L_i, L_j is:
    //   sum_{i<j} C(|L_i|,2) * C(|L_j|,2)
    // This avoids collinear points (3+ on the same line) being counted.
    //
    // Each true parallelogram contributes to two different slopes, so subtract once.
    // Parallelograms are counted via the midpoint trick (diagonals bisect each other).
    // The midpoint trick can overcount when all 4 points are collinear, but such
    // collinear groups are never counted in trap_count, so we subtract collinear
    // pseudo-parallelograms back out.

    use std::collections::{HashMap, HashSet};
    let n = points.len();

    fn gcd(a: i32, b: i32) -> i32 { if b == 0 { a } else { gcd(b, a % b) } }

    // Normalize direction vector so (dx>0) or (dx==0 && dy>0)
    fn normalize(dy: i32, dx: i32) -> (i32, i32) {
      if dx == 0 { return (1, 0); }
      if dy == 0 { return (0, 1); }
      let g = gcd(dy.abs(), dx.abs());
      let (dy, dx) = (dy / g, dx / g);
      if dx < 0 { (-dy, -dx) } else { (dy, dx) }
    }

    let c2 = |x: i64| x * (x - 1) / 2;

    // Map each line (slope, intercept) -> set of point indices on it
    // intercept = ndy * x0 - ndx * y0 (constant for all points on the line)
    let mut line_pts: HashMap<((i32, i32), i64), HashSet<usize>> = HashMap::new();
    for i in 0..n {
      for j in i + 1..n {
        let dy = points[j][1] - points[i][1];
        let dx = points[j][0] - points[i][0];
        let (ndy, ndx) = normalize(dy, dx);
        let intercept =
          ndy as i64 * points[i][0] as i64 - ndx as i64 * points[i][1] as i64;
        let entry = line_pts.entry(((ndy, ndx), intercept)).or_default();
        entry.insert(i);
        entry.insert(j);
      }
    }

    // For each slope, accumulate the point-counts per line
    let mut slope_line_counts: HashMap<(i32, i32), Vec<i64>> = HashMap::new();
    for ((slope, _), pts) in &line_pts {
      slope_line_counts
        .entry(*slope)
        .or_default()
        .push(pts.len() as i64);
    }

    // trap_count = sum over slopes: sum_{i<j} C(mi,2)*C(mj,2)
    // = sum over slopes: [ (sum_i C(mi,2))^2 - sum_i C(mi,2)^2 ] / 2
    let mut trap_count: i64 = 0;
    for counts in slope_line_counts.values() {
      let total: i64 = counts.iter().map(|&c| c2(c)).sum();
      let sq_sum: i64 = counts.iter().map(|&c| { let x = c2(c); x * x }).sum();
      trap_count += (total * total - sq_sum) / 2;
    }

    // Count true parallelograms via midpoint trick:
    // Two pairs sharing a midpoint form a parallelogram (diagonals bisect each other).
    // Overcount only happens when all 4 points are collinear, which we correct below.
    let mut mid_count: HashMap<(i64, i64), i64> = HashMap::new();
    for i in 0..n {
      for j in i + 1..n {
        let mx = points[i][0] as i64 + points[j][0] as i64;
        let my = points[i][1] as i64 + points[j][1] as i64;
        *mid_count.entry((mx, my)).or_insert(0) += 1;
      }
    }
    let para_raw: i64 = mid_count.values().map(|&m| c2(m)).sum();

    // Subtract collinear pseudo-parallelograms:
    // For each line with m>=4 points, count pairs of pairs on that line
    // whose point-sum (== 2*midpoint) is equal.
    let mut collinear_pseudo: i64 = 0;
    for pts_set in line_pts.values() {
      let pts: Vec<usize> = pts_set.iter().copied().collect();
      let m = pts.len();
      if m >= 4 {
        let mut sum_cnt: HashMap<(i64, i64), i64> = HashMap::new();
        for ii in 0..m {
          for jj in ii + 1..m {
            let sx = points[pts[ii]][0] as i64 + points[pts[jj]][0] as i64;
            let sy = points[pts[ii]][1] as i64 + points[pts[jj]][1] as i64;
            *sum_cnt.entry((sx, sy)).or_insert(0) += 1;
          }
        }
        collinear_pseudo += sum_cnt.values().map(|&c| c2(c)).sum::<i64>();
      }
    }

    let true_para = para_raw - collinear_pseudo;
    (trap_count - true_para) as i32
  }
}