2025-12-30：統計梯形的數目Ⅰ。用go語言，給定一組平面上的整數座標點 points，其中每個元素 points[i] = [xi, yi] 表示第 i 個點的位置。要求統計有多少種從這些點中選出四個互不相同的點，使它們可以按某種順序連成一個凸的四邊形，並且該四邊形至少存在一對水平的邊（也就是有兩條邊平行於 x 軸）。注意如果兩條直線的斜率相同則稱它們平行。因為結果可能很大，請將最終計數對 1000000007 取餘後返回。

4 <= points.length <= 100000。

–100000000 <= xi, yi <= 100000000。

所有點兩兩不同。

輸入： 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]。

題目來自力扣3623。

算法過程詳解

1. 按y座標分組計數 算法首先遍歷整個點集 points，目的是統計出有多少個點位於同一水平線（即y座標相同）上。這是通過一個哈希表 pointNum 實現的，其鍵（key）是y座標值，值（value）是對應y座標上點的數量。例如，對於輸入點集 [[1,0],[2,0],[3,0],[2,2],[3,2]]，遍歷後得到的哈希表內容將是 {0: 3, 2: 2}，表示y=0的水平線上有3個點，y=2的水平線上有2個點。

2. 計算每條水平線的邊對數 接下來，算法處理哈希表 pointNum 中的每一組計數。對於一個包含 pNum 個點的水平線，從中任意選擇兩個點都可以形成一條水平的邊。根據組合數學公式，選擇兩個點的組合數（即邊對數）為 C(pNum, 2) = pNum * (pNum - 1) / 2。

   • 在上面的例子中，y=0的點數為3，邊對數 C(3,2) = 3。
   • y=2的點數為2，邊對數 C(2,2) = 1。

3. 組合不同水平線的邊對以形成梯形 一個水平梯形需要兩條水平邊，這兩條邊必須來自不同的水平線。因此，梯形的總數就是所有不同水平線的邊對數兩兩相乘的總和。 算法採用了一種高效的累加技巧來計算這個總和，避免了雙重循環。

   • 它維護兩個變量：ans（最終答案）和 sum（之前已經處理過的所有水平線的邊對數之和）。
   • 在遍歷每條水平線的邊對數 edge 時，當前水平線可以與之前所有水平線形成 edge * sum 個梯形，將此值累加到 ans 中。
   • 然後，將當前水平線的邊對數 edge 加到 sum 中，以便後續水平線使用。
   • 對於我們的例子：處理第一條水平線（y=0，edge=3）時，sum初始為0，所以ans累加0，然後sum變為3。處理第二條水平線（y=2，edge=1）時，ans累加 1 * 3 = 3，得到最終結果。

4. 取模運算 由於結果可能非常大，題目要求對 1000000007 取模。算法在每次進行加法和乘法運算後都立即對中間結果取模，這是為了防止整數溢出並保證結果正確。

複雜度分析

• 總的時間複雜度：O(n) 其中 n 是點的總數。算法主要包含兩次順序遍歷：第一次遍歷所有點（n個）進行分組計數，第二次遍歷哈希表中的不同y座標組（m個）。由於 m（不同y座標的數量）最大可能為 n，但在一般情況下 m << n，整體操作次數與 n 成線性關係。

• 總的額外空間複雜度：O(m) 其中 m 是不同y座標的數量。算法使用了一個哈希表 pointNum 來存儲每個y座標對應的點數量，該哈希表最多需要存儲 m 個鍵值對。除此之外，只使用了幾個整型變量，因此額外的空間消耗主要由哈希表決定。

Go完整代碼如下：

package main

import (
	"fmt"
)

func countTrapezoids(points [][]int) int {
	pointNum := make(map[int]int)
	mod := 1000000007
	ans, sum := 0, 0

	for _, point := range points {
		y := point[1]
		pointNum[y]++
	}

	for _, pNum := range pointNum {
		edge := pNum * (pNum - 1) / 2
		ans = (ans + edge*sum) % mod
		sum = (sum + edge) % mod
	}

	return ans
}

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

Python完整代碼如下：

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

from typing import List
from collections import defaultdict

def countTrapezoids(points: List[List[int]]) -> int:
    pointNum = defaultdict(int)
    MOD = 1000000007
    ans, total = 0, 0
    
    for point in points:
        y = point[1]
        pointNum[y] += 1
    
    for pNum in pointNum.values():
        # 計算從相同y值的點中選2個的組合數
        edge = pNum * (pNum - 1) // 2
        # 與之前的組合形成梯形
        ans = (ans + edge * total) % MOD
        # 累加當前y值的組合數
        total = (total + edge) % MOD
    
    return ans

def main():
    points = [[1, 0], [2, 0], [3, 0], [2, 2], [3, 2]]
    result = countTrapezoids(points)
    print(result)

if __name__ == "__main__":
    main()

C++完整代碼如下：

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

using namespace std;

int countTrapezoids(vector<vector<int>>& points) {
    unordered_map<int, int> pointNum;
    const int MOD = 1000000007;
    long long ans = 0, total = 0;

    for (auto& point : points) {
        int y = point[1];
        pointNum[y]++;
    }

    for (auto& [_, pNum] : pointNum) {
        // 計算從相同y值的點中選2個的組合數
        long long edge = (long long)pNum * (pNum - 1) / 2;
        // 與之前的組合形成梯形
        ans = (ans + edge * total) % MOD;
        // 累加當前y值的組合數
        total = (total + edge) % MOD;
    }

    return ans;
}

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

    return 0;
}