目标
给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点在笛卡尔平面上的坐标。
水平梯形 是一种凸四边形，具有 至少一对 水平边（即平行于 x 轴的边）。两条直线平行当且仅当它们的斜率相同。
返回可以从 points 中任意选择四个不同点组成的 水平梯形 数量。
由于答案可能非常大，请返回结果对 10^9 + 7 取余数后的值。
示例 1：
输入： points = [[1,0],[2,0],[3,0],[2,2],[3,2]]
输出： 3
解释：
有三种不同方式选择四个点组成一个水平梯形：
使用点 [1,0]、[2,0]、[3,2] 和 [2,2]。
使用点 [2,0]、[3,0]、[3,2] 和 [2,2]。
使用点 [1,0]、[3,0]、[3,2] 和 [2,2]。示例 2：
输入： points = [[0,0],[1,0],[0,1],[2,1]]
输出： 1
解释：
只有一种方式可以组成一个水平梯形。说明：
- 4 <= points.length <= 10^5
- –10^8 <= xi, yi <= 10^8
- 所有点两两不同。
思路
有一些二维平面中的点 points，从中选取四个点组成水平梯形，返回水平梯形的数目。
水平梯形是有一对边平行于 x 轴的梯形。直接的想法是根据纵坐标分组，选两组，每组中选两个点。
可以直接计算每组的组合数 C(n, 2) = n * (n - 1) / 2，计算分组组合数的后缀和，根据乘法原理计算即可。
代码
/**
* @date 2025-12-02 0:14
*/
public class CountTrapezoids2623 {
/**
* 执行通过
*/
public int countTrapezoids(int[][] points) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int[] point : points) {
cnt.merge(point[1], 1, Integer::sum);
}
int mod = 1000000007;
for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
Integer c = entry.getValue();
cnt.put(entry.getKey(), (int) ((c * (c - 1L) / 2) % mod));
}
int[] comb = cnt.values().stream().mapToInt(x -> x).toArray();
int n = comb.length;
int[] suffix = new int[n + 1];
for (int i = n - 1; i >= 0; i--) {
suffix[i] = (suffix[i + 1] + comb[i]) % mod;
}
long res = 0L;
for (int i = 0; i < n; i++) {
res = (res + ((long) comb[i] * suffix[i + 1])) % mod;
}
return (int) res;
}
}
性能
