标签： 几何

3625.统计梯形的数目II

目标

给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点在笛卡尔平面上的坐标。

返回可以从 points 中任意选择四个不同点组成的梯形的数量。

梯形 是一种凸四边形，具有 至少一对 平行边。两条直线平行当且仅当它们的斜率相同。

示例 1：

输入： points = [[-3,2],[3,0],[2,3],[3,2],[2,-3]]
输出： 2
解释：
有两种不同方式选择四个点组成一个梯形：
点 [-3,2], [2,3], [3,2], [2,-3] 组成一个梯形。
点 [2,3], [3,2], [3,0], [2,-3] 组成另一个梯形。

示例 2：

输入： points = [[0,0],[1,0],[0,1],[2,1]]
输出： 1
解释：
只有一种方式可以组成一个梯形。

说明：

  • 4 <= points.length <= 500
  • –1000 <= xi, yi <= 1000
  • 所有点两两不同。

思路

和 3623.统计梯形的数目I 类似，本题的斜率可以不是 0，需要考虑垂直于 x 轴的平行线，以及平行四边形重复统计问题。

计算两个坐标点的斜率，并根据斜率分组，再在每一组中根据截距分组。计算斜率需要除法，需要考虑精度问题。需要特殊处理垂线。对于平行四边形，有两对平行的边，在计算时会重复统计。所以还要减去平行四边形的个数，由于其两条对角线的中点是重合的，利用这一性质，按照对角线的中点分组统计。

代码

性能

3623.统计梯形的数目I

目标

给你一个二维整数数组 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;
    }
}

性能

812.最大三角形面积

目标

给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在 10^-5 内的答案将会视为正确答案。

示例 1：

输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出：2.00000
解释：输入中的 5 个点如上图所示，红色的三角形面积最大。

示例 2：

输入：points = [[1,0],[0,0],[0,1]]
输出：0.50000

提示：

  • 3 <= points.length <= 50
  • -50 <= xi, yi <= 50
  • 给出的所有点 互不相同

思路

暴力解，三层循环，三角形面积可以使用向量的叉积计算。

向量的叉积表示这两个向量构成的平行四边形面积，除以 2 就是三角形的面积。

向量 (x1, y1) 与 (x2, y2) 的叉积等于 |x1 * y2 - x2 * y1|。

代码


/**
 * @date 2025-09-27 21:35
 */
public class LargestTriangleArea812 {

    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double res = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    int p1 = points[i][0];
                    int q1 = points[i][1];
                    int p2 = points[j][0];
                    int q2 = points[j][1];
                    int p3 = points[k][0];
                    int q3 = points[k][1];
                    res = Math.max(res, Math.abs((p2 - p1) * (q3 - q1) - (p3 - p1) * (q2 - q1)));
                }
            }
        }
        return res / 2;
    }
}

性能

3027.人员站位的方案数II

目标

给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。

我们定义 x 轴的正方向为 右 （x 轴递增的方向），x 轴的负方向为 左 （x 轴递减的方向）。类似的，我们定义 y 轴的正方向为 上 （y 轴递增的方向），y 轴的负方向为 下 （y 轴递减的方向）。

你需要安排这 n 个人的站位，这 n 个人中包括 Alice 和 Bob 。你需要确保每个点处 恰好 有 一个 人。同时，Alice 想跟 Bob 单独玩耍，所以 Alice 会以 Alice 的坐标为 左上角 ，Bob 的坐标为 右下角 建立一个矩形的围栏（注意，围栏可能 不 包含任何区域，也就是说围栏可能是一条线段）。如果围栏的 内部 或者 边缘 上有任何其他人，Alice 都会难过。

请你在确保 Alice 不会 难过的前提下，返回 Alice 和 Bob 可以选择的 点对 数目。

注意，Alice 建立的围栏必须确保 Alice 的位置是矩形的左上角，Bob 的位置是矩形的右下角。比方说，以 (1, 1) ，(1, 3) ，(3, 1) 和 (3, 3) 为矩形的四个角，给定下图的两个输入，Alice 都不能建立围栏，原因如下：

图一中，Alice 在 (3, 3) 且 Bob 在 (1, 1) ，Alice 的位置不是左上角且 Bob 的位置不是右下角。
图二中，Alice 在 (1, 3) 且 Bob 在 (1, 1) ，Bob 的位置不是在围栏的右下角。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：0
解释：没有办法可以让 Alice 的围栏以 Alice 的位置为左上角且 Bob 的位置为右下角。所以我们返回 0 。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]
输出：2
解释：总共有 2 种方案安排 Alice 和 Bob 的位置，使得 Alice 不会难过：
- Alice 站在 (4, 4) ，Bob 站在 (6, 2) 。
- Alice 站在 (2, 6) ，Bob 站在 (4, 4) 。
不能安排 Alice 站在 (2, 6) 且 Bob 站在 (6, 2) ，因为站在 (4, 4) 的人处于围栏内。

示例 3：

输入：points = [[3,1],[1,3],[1,1]]
输出：2
解释：总共有 2 种方案安排 Alice 和 Bob 的位置，使得 Alice 不会难过：
- Alice 站在 (1, 1) ，Bob 站在 (3, 1) 。
- Alice 站在 (1, 3) ，Bob 站在 (1, 1) 。
不能安排 Alice 站在 (1, 3) 且 Bob 站在 (3, 1) ，因为站在 (1, 1) 的人处于围栏内。
注意围栏是可以不包含任何面积的，上图中第一和第二个围栏都是合法的。

说明：

  • 2 <= n <= 1000
  • points[i].length == 2
  • -10^9 <= points[i][0], points[i][1] <= 10^9
  • points[i] 点对两两不同。

思路

代码

性能

3025.人员站位的方案数I

目标

给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。

计算点对 (A, B) 的数量，其中

  • A 在 B 的左上角，并且
  • 它们形成的长方形中（或直线上）没有其它点（包括边界）。

返回数量。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：0
解释：
没有办法选择 A 和 B，使得 A 在 B 的左上角。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]
输出：2
解释：
左边的是点对 (points[1], points[0])，其中 points[1] 在 points[0] 的左上角，并且形成的长方形内部是空的。
中间的是点对 (points[2], points[1])，和左边的一样是合法的点对。
右边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角，但 points[1] 在长方形内部，所以不是一个合法的点对。

示例 3：

输入：points = [[3,1],[1,3],[1,1]]
输出：2
解释：
左边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角并且在它们形成的直线上没有其它点。注意两个点形成一条线的情况是合法的。
中间的是点对 (points[1], points[2])，和左边一样也是合法的点对。
右边的是点对 (points[1], points[0])，它不是合法的点对，因为 points[2] 在长方形的边上。

说明：

  • 2 <= n <= 50
  • points[i].length == 2
  • 0 <= points[i][0], points[i][1] <= 50
  • points[i] 点对两两不同。

思路

代码

性能