登录[Python3/Java/C++/Go/TypeScript] 一题一解：哈希表+枚举（清晰题解）
方法一：哈希表 + 枚举
我们可以把所有点两两组合，计算出每一对点所对应的直线的斜率和截距，并使用哈希表进行记录，计算斜率相同且截距不同的直线两两组合得到的数量之和。注意，对于平行四边形，我们在上述计算中会被重复计算两次，因此我们需要将其减去。
平行四边形的对角线中点重合，因此我们同样把所有点两两组合，计算出每一对点的中点坐标和斜率，并使用哈希表进行记录，计算斜率相同且中点坐标相同的点对两两组合得到的数量之和。
具体地，我们使用两个哈希表 $\textit{cnt1}$ 和 $\textit{cnt2}$ 分别记录以下信息：
- 其中 $\textit{cnt1}$ 记录斜率 $k$ 和截距 $b$ 出现的次数，键为斜率 $k$，值为另一个哈希表，记录截距 $b$ 出现的次数；
- 其中 $\textit{cnt2}$ 记录点对的中点坐标和斜率 $k$ 出现的次数，键为点对的中点坐标 $p$，值为另一个哈希表，记录斜率 $k$ 出现的次数。
对于点对 $(x_1, y_1)$ 和 $(x_2, y_2)$，我们记 $dx = x_2 - x_1$，并且 $dy = y_2 - y_1$。如果 $dx = 0$，则说明两点在同一条垂直线上，我们记斜率 $k = +\infty$，截距 $b = x_1$；否则斜率 $k = \frac{dy}{dx}$，截距 $b = \frac{y_1 \cdot dx - x_1 \cdot dy}{dx}$。点对的中点坐标 $p$ 可以表示为 $p = (x_1 + x_2 + 2000) \cdot 4000 + (y_1 + y_2 + 2000)$，这里加上偏移量是为了避免负数。
接下来，我们遍历所有点对，计算出对应的斜率 $k$、截距 $b$ 和中点坐标 $p$，并更新哈希表 $\textit{cnt1}$ 和 $\textit{cnt2}$。
然后，我们遍历哈希表 $\textit{cnt1}$，对于每一个斜率 $k$，我们计算所有截距 $b$ 出现次数的两两组合之和，并累加到答案中。最后，我们遍历哈希表 $\textit{cnt2}$，对于每一个中点坐标 $p$，我们计算所有斜率 $k$ 出现次数的两两组合之和，并从答案中减去。
###python
class Solution:
def countTrapezoids(self, points: List[List[int]]) -> int:
n = len(points)
# cnt1: k -> (b -> count)
cnt1: dict[float, dict[float, int]] = defaultdict(lambda: defaultdict(int))
# cnt2: p -> (k -> count)
cnt2: dict[int, dict[float, int]] = defaultdict(lambda: defaultdict(int))
for i in range(n):
x1, y1 = points[i]
for j in range(i):
x2, y2 = points[j]
dx, dy = x2 - x1, y2 - y1
if dx == 0:
k = 1e9
b = x1
else:
k = dy / dx
b = (y1 * dx - x1 * dy) / dx
cnt1[k][b] += 1
p = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000)
cnt2[p][k] += 1
ans = 0
for e in cnt1.values():
s = 0
for t in e.values():
ans += s * t
s += t
for e in cnt2.values():
s = 0
for t in e.values():
ans -= s * t
s += t
return ans
###java
class Solution {
public int countTrapezoids(int[][] points) {
int n = points.length;
Map<Double, Map<Double, Integer>> cnt1 = new HashMap<>(n * n);
Map<Integer, Map<Double, Integer>> cnt2 = new HashMap<>(n * n);
for (int i = 0; i < n; ++i) {
int x1 = points[i][0], y1 = points[i][1];
for (int j = 0; j < i; ++j) {
int x2 = points[j][0], y2 = points[j][1];
int dx = x2 - x1, dy = y2 - y1;
double k = dx == 0 ? Double.MAX_VALUE : 1.0 * dy / dx;
double b = dx == 0 ? x1 : 1.0 * (y1 * dx - x1 * dy) / dx;
if (k == -0.0) {
k = 0.0;
}
if (b == -0.0) {
b = 0.0;
}
cnt1.computeIfAbsent(k, _ -> new HashMap<>()).merge(b, 1, Integer::sum);
int p = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000);
cnt2.computeIfAbsent(p, _ -> new HashMap<>()).merge(k, 1, Integer::sum);
}
}
int ans = 0;
for (var e : cnt1.values()) {
int s = 0;
for (int t : e.values()) {
ans += s * t;
s += t;
}
}
for (var e : cnt2.values()) {
int s = 0;
for (int t : e.values()) {
ans -= s * t;
s += t;
}
}
return ans;
}
}
###cpp
class Solution {
public:
int countTrapezoids(vector<vector<int>>& points) {
int n = points.size();
unordered_map<double, unordered_map<double, int>> cnt1;
unordered_map<int, unordered_map<double, int>> cnt2;
cnt1.reserve(n * n);
cnt2.reserve(n * n);
for (int i = 0; i < n; ++i) {
int x1 = points[i][0], y1 = points[i][1];
for (int j = 0; j < i; ++j) {
int x2 = points[j][0], y2 = points[j][1];
int dx = x2 - x1, dy = y2 - y1;
double k = (dx == 0 ? 1e9 : 1.0 * dy / dx);
double b = (dx == 0 ? x1 : 1.0 * (1LL * y1 * dx - 1LL * x1 * dy) / dx);
cnt1[k][b] += 1;
int p = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000);
cnt2[p][k] += 1;
}
}
int ans = 0;
for (auto& [_, e] : cnt1) {
int s = 0;
for (auto& [_, t] : e) {
ans += s * t;
s += t;
}
}
for (auto& [_, e] : cnt2) {
int s = 0;
for (auto& [_, t] : e) {
ans -= s * t;
s += t;
}
}
return ans;
}
};
###go
func countTrapezoids(points [][]int) int {
n := len(points)
cnt1 := make(map[float64]map[float64]int, n*n)
cnt2 := make(map[int]map[float64]int, n*n)
for i := 0; i < n; i++ {
x1, y1 := points[i][0], points[i][1]
for j := 0; j < i; j++ {
x2, y2 := points[j][0], points[j][1]
dx, dy := x2-x1, y2-y1
var k, b float64
if dx == 0 {
k = 1e9
b = float64(x1)
} else {
k = float64(dy) / float64(dx)
b = float64(int64(y1)*int64(dx)-int64(x1)*int64(dy)) / float64(dx)
}
if cnt1[k] == nil {
cnt1[k] = make(map[float64]int)
}
cnt1[k][b]++
p := (x1+x2+2000)*4000 + (y1 + y2 + 2000)
if cnt2[p] == nil {
cnt2[p] = make(map[float64]int)
}
cnt2[p][k]++
}
}
ans := 0
for _, e := range cnt1 {
s := 0
for _, t := range e {
ans += s * t
s += t
}
}
for _, e := range cnt2 {
s := 0
for _, t := range e {
ans -= s * t
s += t
}
}
return ans
}
###ts
function countTrapezoids(points: number[][]): number {
const n = points.length;
const cnt1: Map<number, Map<number, number>> = new Map();
const cnt2: Map<number, Map<number, number>> = new Map();
for (let i = 0; i < n; i++) {
const [x1, y1] = points[i];
for (let j = 0; j < i; j++) {
const [x2, y2] = points[j];
const [dx, dy] = [x2 - x1, y2 - y1];
const k = dx === 0 ? 1e9 : dy / dx;
const b = dx === 0 ? x1 : (y1 * dx - x1 * dy) / dx;
if (!cnt1.has(k)) {
cnt1.set(k, new Map());
}
const mapB = cnt1.get(k)!;
mapB.set(b, (mapB.get(b) || 0) + 1);
const p = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000);
if (!cnt2.has(p)) {
cnt2.set(p, new Map());
}
const mapK = cnt2.get(p)!;
mapK.set(k, (mapK.get(k) || 0) + 1);
}
}
let ans = 0;
for (const e of cnt1.values()) {
let s = 0;
for (const t of e.values()) {
ans += s * t;
s += t;
}
}
for (const e of cnt2.values()) {
let s = 0;
for (const t of e.values()) {
ans -= s * t;
s += t;
}
}
return ans;
}
时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 是点的数量。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~
