Hard
题目描述
给你一个二维整数数组 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- 所有点都是两两不同的。
解题思路
解题思路
这道题要求计算能够形成梯形的四点组合数。梯形的关键特征是至少有一对平行边，即至少有两条边具有相同的斜率。
核心思路：
斜率计算与标准化：对于任意两点，计算其连线的斜率。为避免浮点精度问题，使用
(dy, dx)的最简分数形式表示斜率，通过最大公约数(GCD)进行约简，并统一符号。分组统计：将所有点对按斜率分组。对于每个斜率组，如果有 k 条线段，则可以选择
C(k,2) = k*(k-1)/2种方式作为梯形的平行边。排除共端点情况：两条线段如果共享端点，无法构成四边形，需要排除这些情况。
处理平行四边形重复计数：平行四边形有两对平行边，会被计算两次，需要减去重复计数。平行四边形的判定条件是四个点形成的对角线中点重合。
算法步骤：
- 枚举所有点对，计算标准化斜率
- 按斜率分组，统计每组的有效线段对数
- 识别并减去平行四边形的重复计数
- 返回最终的梯形数量
时间复杂度为 O(n²)，空间复杂度为 O(n²)。
代码实现
class Solution {
public:
int countTrapezoids(vector<vector<int>>& points) {
int n = points.size();
map<pair<int, int>, vector<pair<int, int>>> slopeMap;
auto gcd = [](int a, int b) {
return b == 0 ? a : __gcd(abs(a), abs(b));
};
auto normalize = [&](int dy, int dx) -> pair<int, int> {
if (dx == 0) return {1, 0};
if (dy == 0) return {0, 1};
int g = gcd(dy, dx);
dy /= g;
dx /= g;
if (dx < 0) {
dy = -dy;
dx = -dx;
}
return {dy, dx};
};
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dy = points[j][1] - points[i][1];
int dx = points[j][0] - points[i][0];
auto slope = normalize(dy, dx);
slopeMap[slope].push_back({i, j});
}
}
long long result = 0;
for (auto& [slope, segments] : slopeMap) {
int k = segments.size();
if (k < 2) continue;
long long total = (long long)k * (k - 1) / 2;
set<pair<int, int>> endpoints;
for (auto& seg : segments) {
endpoints.insert(seg);
}
for (int i = 0; i < k; i++) {
for (int j = i + 1; j < k; j++) {
auto& seg1 = segments[i];
auto& seg2 = segments[j];
if (seg1.first == seg2.first || seg1.first == seg2.second ||
seg1.second == seg2.first || seg1.second == seg2.second) {
total--;
}
}
}
result += total;
}
map<pair<int, int>, int> midpointCount;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int mx = points[i][0] + points[j][0];
int my = points[i][1] + points[j][1];
midpointCount[{mx, my}]++;
}
}
for (auto& [midpoint, count] : midpointCount) {
if (count >= 2) {
result -= (long long)count * (count - 1) / 2;
}
}
return result;
}
};
class Solution:
def countTrapezoids(self, points: List[List[int]]) -> int:
from collections import defaultdict
from math import gcd
n = len(points)
slope_map = defaultdict(list)
def normalize_slope(dy, dx):
if dx == 0:
return (1, 0)
if dy == 0:
return (0, 1)
g = gcd(abs(dy), abs(dx))
dy //= g
dx //= g
if dx < 0:
dy, dx = -dy, -dx
return (dy, dx)
for i in range(n):
for j in range(i + 1, n):
dy = points[j][1] - points[i][1]
dx = points[j][0] - points[i][0]
slope = normalize_slope(dy, dx)
slope_map[slope].append((i, j))
result = 0
for slope, segments in slope_map.items():
k = len(segments)
if k < 2:
continue
total = k * (k - 1) // 2
for i in range(k):
for j in range(i + 1, k):
seg1 = segments[i]
seg2 = segments[j]
if (seg1[0] == seg2[0] or seg1[0] == seg2[1] or
seg1[1] == seg2[0] or seg1[1] == seg2[1]):
total -= 1
result += total
midpoint_count = defaultdict(int)
for i in range(n):
for j in range(i + 1, n):
mx = points[i][0] + points[j][0]
my = points[i][1] + points[j][1]
midpoint_count[(mx, my)] += 1
for count in midpoint_count.values():
if count >= 2:
result -= count * (count - 1) // 2
return result
public class Solution {
public int CountTrapezoids(int[][] points) {
int n = points.Length;
var slopeMap = new Dictionary<(int, int), List<(int, int)>>();
int Gcd(int a, int b) {
a = Math.Abs(a);
b = Math.Abs(b);
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
(int, int) NormalizeSlope(int dy, int dx) {
if (dx == 0) return (1, 0);
if (dy == 0) return (0, 1);
int g = Gcd(dy, dx);
dy /= g;
dx /= g;
if (dx < 0) {
dy = -dy;
dx = -dx;
}
return (dy, dx);
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dy = points[j][1] - points[i][1];
int dx = points[j][0] - points[i][0];
var slope = NormalizeSlope(dy, dx);
if (!slopeMap.ContainsKey(slope)) {
slopeMap[slope] = new List<(int, int)>();
}
slopeMap[slope].Add((i, j));
}
}
long result = 0;
foreach (var kvp in slopeMap) {
var segments = kvp.Value;
int k = segments.Count;
if (k < 2) continue;
long total = (long)k * (k - 1) / 2;
for (int i = 0; i < k; i++) {
for (int j = i + 1; j < k; j++) {
var seg1 = segments[i];
var seg2 = segments[j];
if (seg1.Item1 == seg2.Item1 || seg1.Item1 == seg2.Item2 ||
seg1.Item2 == seg2.Item1 || seg1.Item2 == seg2.Item2) {
total--;
}
}
}
result += total;
}
var midpointCount = new Dictionary<(int, int), int>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int mx = points[i][0] + points[j][0];
int my = points[i][1] + points[j][1];
var midpoint = (mx, my);
if (!midpointCount.ContainsKey(midpoint)) {
midpointCount[midpoint] = 0;
}
midpointCount[midpoint]++;
}
}
foreach (var count in midpointCount.Values) {
if (count >= 2) {
result -= (long)count * (count - 1) / 2;
}
}
return (int)result;
}
}
var countTrapezoids = function(points) {
const n = points.length;
let count = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const slopeMap = new Map();
for (let k = 0; k < n; k++) {
if (k === i || k === j) continue;
const slope1 = getSlope(points[i], points[k]);
const slope2 = getSlope(points[j], points[k]);
const key = slope1 + "," + slope2;
slopeMap.set(key, (slopeMap.get(key) || 0) + 1);
}
for (let k = j + 1; k < n; k++) {
if (k === i) continue;
for (let l = k + 1; l < n; l++) {
if (l === i || l === j) continue;
if (isTrapezoid(points[i], points[j], points[k], points[l])) {
count++;
}
}
}
}
}
return count / 3;
};
function getSlope(p1, p2) {
if (p1[0] === p2[0]) return "inf";
return (p2[1] - p1[1]) / (p2[0] - p1[0]);
}
function isTrapezoid(p1, p2, p3, p4) {
const slopes = [
getSlope(p1, p2),
getSlope(p2, p3),
getSlope(p3, p4),
getSlope(p4, p1),
getSlope(p1, p3),
getSlope(p2, p4)
];
return slopes[0] === slopes[2] || slopes[1] === slopes[3] || slopes[4] === slopes[0] || slopes[4] === slopes[1] || slopes[5] === slopes[0] || slopes[5] === slopes[1] || slopes[5] === slopes[2] || slopes[5] === slopes[3];
}
var countTrapezoids = function(points) {
const n = points.length;
let count = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
for (let l = k + 1; l < n; l++) {
if (isTrapezoid(points[i], points[j], points[k], points[l])) {
count++;
}
}
}
}
}
return count;
};
function getSlope(p1, p2) {
if (p1[0] === p2[0]) return Infinity;
return (p2[1] - p1[1]) / (p2[0] - p1[0]);
}
function isTrapezoid(p1, p2, p3, p4) {
const points = [p1, p2, p3, p4];
const slopes = [];
for (let i = 0; i < 4; i++) {
for (let j = i + 1; j < 4; j++) {
slopes.push(getSlope(points[i], points[j]));
}
}
const slopeCount = new Map();
for (let slope of slopes) {
slopeCount.set(slope, (slopeCount.get(slope) || 0) + 1);
}
for (let count of slopeCount.values()) {
if (count >= 2) return true;
}
return false;
}
复杂度分析
| 项目 | 复杂度 |
|---|---|
| 时间复杂度 | O(n²) |
| 空间复杂度 | O(n²) |
其中 n 是点的数量。时间复杂度主要来自于枚举所有点对计算斜率，以及对每个斜率组内的线段对进行检查。空间复杂度来自于存储所有线段的斜率信息和中点信息。