以下是 LeetCode 3625. 统计梯形的数目 II 的 Rust 实现。核心思路1. 统计所有有一组平行对边的四边形枚举所有点对构成的线段按斜率 → 截距分组。同一斜率下从不同截距的直线各选一条边即可构成一组平行对边。累加所有这样的组合数。2. 减去平行四边形的重复计数平行四边形有两组平行对边会在步骤 1 中被统计 2 次。利用平行四边形对边中点相同的性质按中点 → 斜率分组统计平行四边形数量从答案中扣除。为了避免浮点精度问题斜率和截距均用约分后的整数对 (分子, 分母) 表示。rustuse std::collections::HashMap;impl Solution {pub fn count_trapezoids(points: VecVeci32) - i32 {let n points.len();// cnt1: 斜率(约分后的 dy,dx) - 截距(约分后的分子,分母) - 该直线上的边数let mut cnt1: HashMap(i32, i32), HashMap(i32, i32), i32 HashMap::new();// cnt2: 中点编码 - 斜率 - 边数let mut cnt2: HashMapi32, HashMap(i32, i32), i32 HashMap::new();for i in 0..n {let x1 points[i][0];let y1 points[i][1];for j in 0..i {let x2 points[j][0];let y2 points[j][1];let dx x2 - x1;let dy y2 - y1;let k: (i32, i32); // 斜率let b: (i32, i32); // 截距if dx 0 {// 垂直线斜率无穷大用 (1, 0) 标记截距为 x 坐标k (1, 0);b (x1, 1);} else {// 斜率约分let g gcd(dy.abs(), dx.abs());let mut ndy dy / g;let mut ndx dx / g;if ndx 0 {ndy -ndy;ndx -ndx;}k (ndy, ndx);// 截距 b (y1*dx - x1*dy) / dx同样约分let bn y1 * dx - x1 * dy;let bd dx;let bg gcd(bn.abs(), bd.abs());let mut nbn bn / bg;let mut nbd bd / bg;if nbd 0 {nbn -nbn;nbd -nbd;}b (nbn, nbd);}*cnt1.entry(k).or_insert_with(HashMap::new).entry(b).or_insert(0) 1;// 中点编码为单个整数避免浮点数let p (x1 x2 2000) * 4000 (y1 y2 2000);*cnt2.entry(p).or_insert_with(HashMap::new).entry(k).or_insert(0) 1;}}let mut ans: i64 0;// 步骤1统计所有有一组平行对边的四边形含平行四边形for (_, m) in cnt1 {let mut s 0i64;for (_, c) in m {ans s * c as i64; // 从之前的直线选1条 当前直线选1条s c as i64;}}// 步骤2减去平行四边形的重复计数// 平行四边形在 cnt1 中被算了2次这里减去多算的1次for (_, m) in cnt2 {let mut s 0i64;for (_, c) in m {ans - s * c as i64; // 同一中点同一斜率的两条边构成平行四边形的一组对边s c as i64;}}ans as i32}}fn gcd(mut a: i32, mut b: i32) - i32 {while b ! 0 {let t b;b a % b;a t;}a}复杂度分析- 时间复杂度O(n^2)其中 n 为点的数量。枚举所有 O(n^2) 条边哈希表操作均摊 O(1)。- 空间复杂度O(n^2)最坏情况下每条边对应唯一的斜率/截距/中点组合。