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 轴的平行线,以及平行四边形重复统计问题。

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

代码

性能

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注