2026-01-01：统计梯形的数目Ⅱ。用go语言，给你若干平面上的整数坐标点 points，其中每个 points[i] = [xi, yi] 表示第 i 个点的位置。请统计从这些点中任取 4 个不同点，能拼成梯形的不同方法数。

这里把梯形理解为：四个顶点按顺序连成的四边形是凸的，且至少有一对对边互相平行（也就是那两条边的斜率相同）。返回满足该条件的四点组合总数。

4 <= points.length <= 500。

–1000 <= xi, yi <= 1000。

所有点两两不同。

输入： 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] 组成另一个梯形。

题目来自力扣3625。

🔍 算法步骤详解

步骤一：遍历所有边并计算关键特征

代码首先遍历所有不重复的点对（由 i 和 j 索引确保），对于每两个点构成的线段，计算三个关键几何特征：

1. 斜率 (k)：判断线段是否平行的依据。如果线段不垂直于x轴，斜率 k = (y2 - y1) / (x2 - x1)；如果垂直于x轴（x1 == x2），则用一个极大值（如 inf = 1e9+7）来特殊标记。
2. 截距 (b)：用于区分在同一条直线上的线段（共线）还是仅仅平行但不在同一直线上的线段。对于非垂直线，截距通过公式 b = (y1*dx - x1*dy)/dx 计算；对于垂直线，则直接用 x1 作为截距的标识。
3. 中点指纹 (mid)：用于后续识别平行四边形。代码将线段中点坐标 ((x1+x2)/2, (y1+y2)/2) 的2倍和（即 (x1+x2), (y1+y2)）进行线性变换并编码为一个 float64 值，作为该线段中点的唯一指纹。

计算完这些特征后，代码将它们存入两个哈希表（在Go中是 map）：

• slopeToIntercept：以斜率 k 为键，存储所有具有该斜率的线段对应的截距 b。
• midToSlope：以中点指纹 mid 为键，存储所有具有该中点的线段对应的斜率 k。

步骤二：统计候选四边形（包含平行四边形）

这一步骤的目标是找出所有由两条平行且不共线的边构成的四边形。代码遍历 slopeToIntercept 哈希表。

• 对于每一个斜率 k，获取所有具有该斜率的线段的截距列表。
• 然后，根据截距 b 对这些线段进行分组计数。关键点在于：截距不同的线段，意味着它们互相平行但不在同一直线上，这样的两条线段可以作为梯形的“上底”和“下底”。
• 统计时采用了一种高效的累加方法：遍历不同截距组，将 当前截距组的线段数量 与 之前所有截距组的线段数量之和 相乘，并将结果累加到答案 ans 中。这样就算出了所有至少有一对平行边的四边形数量，其中包含了平行四边形。

步骤三：减去平行四边形的数量

平行四边形有两对平行边，因此在步骤二中，它会被统计两次（分别以两对平行边各统计一次）。但梯形定义中平行四边形只应算作一个，所以需要减去多算的一次。

• 代码遍历 midToSlope 哈希表。
• 对于每一个中点指纹 mid，获取所有具有该中点的线段的斜率列表。
• 然后，根据斜率 k 对这些线段进行分组计数。关键点在于：如果两条线段共享同一个中点且斜率相同，那么它们很可能是一个平行四边形的两条对角线，对应的四条边就构成了一个平行四边形。
• 同样使用累加方法：对于同一中点下的同一斜率，计算其线段组合数，并从总答案 ans 中减去这些组合数。这样就扣除了因平行四边形重复统计而多出来的数量。

步骤四：返回结果

经过步骤二和步骤三的处理，ans 中存储的就是纯梯形的数量（包括只有一对平行边的梯形和有一对平行边的平行四边形）。代码最终返回这个值。

⏱️ 复杂度分析

• 总的时间复杂度：O(n²)。算法的主要开销在于第一步，需要遍历所有点对，数量级为 O(n²)。后续对哈希表的遍历操作，其数据量也源于点对数量，因此整体复杂度为 O(n²)。
• 总的额外空间复杂度：O(n²)。算法需要两个哈希表来存储所有边（点对）的特征信息。在最坏情况下，每条边都有唯一的特征，因此需要存储 O(n²) 个元素。

Go完整代码如下：

package main

import (
	"fmt"
)

func countTrapezoids(points [][]int) int {
	n := len(points)
	inf := 1e9 + 7
	slopeToIntercept := make(map[float64][]float64)
	midToSlope := make(map[float64][]float64)
	ans := 0

	for i := 0; i < n; i++ {
		x1, y1 := points[i][0], points[i][1]
		for j := i + 1; j < n; j++ {
			x2, y2 := points[j][0], points[j][1]
			dx := x1 - x2
			dy := y1 - y2

			var k, b float64
			if x2 == x1 {
				k = inf
				b = float64(x1)
			} else {
				k = float64(y2-y1) / float64(x2-x1)
				b = float64(y1*dx-x1*dy) / float64(dx)
			}

			mid := float64((x1+x2)*10000 + (y1 + y2))
			slopeToIntercept[k] = append(slopeToIntercept[k], b)
			midToSlope[mid] = append(midToSlope[mid], k)
		}
	}

	for _, sti := range slopeToIntercept {
		if len(sti) == 1 {
			continue
		}

		cnt := make(map[float64]int)
		for _, bVal := range sti {
			cnt[bVal]++
		}

		totalSum := 0
		for _, count := range cnt {
			ans += totalSum * count
			totalSum += count
		}
	}

	for _, mts := range midToSlope {
		if len(mts) == 1 {
			continue
		}

		cnt := make(map[float64]int)
		for _, kVal := range mts {
			cnt[kVal]++
		}

		totalSum := 0
		for _, count := range cnt {
			ans -= totalSum * count
			totalSum += count
		}
	}

	return ans
}

func main() {
	points := [][]int{{-3, 2}, {3, 0}, {2, 3}, {3, 2}, {2, -3}}
	result := countTrapezoids(points)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def count_trapezoids(points):
    n = len(points)
    INF = float('inf')
    slope_to_intercept = {}
    mid_to_slope = {}
    ans = 0

    for i in range(n):
        x1, y1 = points[i]
        for j in range(i + 1, n):
            x2, y2 = points[j]
            dx = x1 - x2
            dy = y1 - y2

            if dx == 0:
                k = INF
                b = float(x1)
            else:
                k = (y2 - y1) / (x2 - x1)
                b = (y1 * dx - x1 * dy) / dx

            mid = (x1 + x2) * 10000 + (y1 + y2)
            
            if k not in slope_to_intercept:
                slope_to_intercept[k] = []
            slope_to_intercept[k].append(b)
            
            if mid not in mid_to_slope:
                mid_to_slope[mid] = []
            mid_to_slope[mid].append(k)

    # 处理相同斜率的线段
    for sti in slope_to_intercept.values():
        if len(sti) == 1:
            continue
        
        cnt = {}
        for b_val in sti:
            cnt[b_val] = cnt.get(b_val, 0) + 1
        
        total_sum = 0
        for count in cnt.values():
            ans += total_sum * count
            total_sum += count

    # 处理相同中点的线段
    for mts in mid_to_slope.values():
        if len(mts) == 1:
            continue
        
        cnt = {}
        for k_val in mts:
            cnt[k_val] = cnt.get(k_val, 0) + 1
        
        total_sum = 0
        for count in cnt.values():
            ans -= total_sum * count
            total_sum += count

    return ans


def main():
    points = [[-3, 2], [3, 0], [2, 3], [3, 2], [2, -3]]
    result = count_trapezoids(points)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>

using namespace std;

int countTrapezoids(vector<vector<int>>& points) {
    int n = points.size();
    double inf = 1e9 + 7;
    unordered_map<double, vector<double>> slopeToIntercept;
    unordered_map<double, vector<double>> midToSlope;
    int ans = 0;

    for (int i = 0; i < n; i++) {
        int x1 = points[i][0];
        int y1 = points[i][1];
        for (int j = i + 1; j < n; j++) {
            int x2 = points[j][0];
            int y2 = points[j][1];
            int dx = x1 - x2;
            int dy = y1 - y2;

            double k, b;
            if (x2 == x1) {
                k = inf;
                b = static_cast<double>(x1);
            } else {
                k = static_cast<double>(y2 - y1) / (x2 - x1);
                b = static_cast<double>(y1 * dx - x1 * dy) / dx;
            }

            double mid = (x1 + x2) * 10000.0 + (y1 + y2);
            slopeToIntercept[k].push_back(b);
            midToSlope[mid].push_back(k);
        }
    }

    // 处理相同斜率的线段
    for (auto& kv : slopeToIntercept) {
        auto& sti = kv.second;
        if (sti.size() == 1) continue;

        unordered_map<double, int> cnt;
        for (double bVal : sti) {
            cnt[bVal]++;
        }

        int totalSum = 0;
        for (auto& countKv : cnt) {
            ans += totalSum * countKv.second;
            totalSum += countKv.second;
        }
    }

    // 处理相同中点的线段
    for (auto& kv : midToSlope) {
        auto& mts = kv.second;
        if (mts.size() == 1) continue;

        unordered_map<double, int> cnt;
        for (double kVal : mts) {
            cnt[kVal]++;
        }

        int totalSum = 0;
        for (auto& countKv : cnt) {
            ans -= totalSum * countKv.second;
            totalSum += countKv.second;
        }
    }

    return ans;
}

int main() {
    vector<vector<int>> points = {{-3, 2}, {3, 0}, {2, 3}, {3, 2}, {2, -3}};
    int result = countTrapezoids(points);
    cout << result << endl;
    return 0;
}