3623 统计梯形的数目 I

题目描述#

给定一个二维整数数组 points，其中 points[i] = [x_i, y_i] 表示平面上的一个点。任意挑选四个不同的点，若能够构成至少一对水平边（平行 x 轴）的凸四边形，则称其为 水平梯形。请返回可以组成的水平梯形数量，对 1_000_000_007 取模。

思路#

要形成水平梯形，至少需要两个不同的水平线，各自挑选两个点充当上下底。若某条水平线拥有 c 个点，则在该线上选出一对点的方式为 C(c, 2)。

于是问题化为：对所有 y 坐标分组，统计 C(c, 2)，然后在不同的水平线之间配对。若我们依次遍历每条水平线产生的 k = C(c, 2)，用变量 s 累积之前所有水平线的 k，则当前线能够与之前任意一条组成梯形的数量为 s * k。

遍历完成后即可得到答案；过程中都使用 long 防止溢出，最后对 MOD 取余。

通过排列组合的方式化简本题目

代码#

class Solution {
    private static final int MOD = 1_000_000_007;

    public int countTrapezoids(int[][] points) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int[] p : points) {
            cnt.merge(p[1], 1, Integer::sum); // 统计每条水平线上的点数
        }
        long ans = 0L, s = 0L;
        for (int c : cnt.values()) {
            long k = (long) c * (c - 1) / 2; // 当前水平线可选的点对数
            ans = (ans + s * k) % MOD;
            s += k;
        }
        return (int) ans;
    }
}