題目連結(https://leetcode.com/problems/largest-triangle-area/?envType=daily-question&envId=2025-09-27)

Given an array of points on the X-Y plane points where points[i] = [xi, yi], return the area of the largest triangle that can be formed by any three different points. Answers within 10＾-5 of the actual answer will be accepted.

最近的每日一題好像都跟三角形有關？這題太數學了面試感覺不太會考
等比較不忙後分享一下演算法比較複雜的題目，作業快完蛋了嗚嗚

1. Repeat（題目重複確認）

• 輸入：一些平面上的點座標
• 輸出：最大的三角形面積
• 前提：
  • 3 <= points.length <= 50
  • 50 <= xi, yi <= 50

2. Examples（舉例確認理解）

Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2.00000

3. Approach（解題思路）

方法 1：brute force

• 遍歷所有可能的三點組合 (i, j, k)，其中 i < j < k，用外積法求面積
• 時間複雜度：O(n^3)
• 空間複雜度：O(1)

其他方法 ：海龍公式、行列式法

• 時間複雜度也不會下降，並沒有比較好

4. Code（C++）

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
	        int n = points.size(); 
        if (n < 3) {//但是題目限制大於三個點，所以這段不用寫也行
            return 0.0; // 點少於三個無法形成三角形
        }

        double maxarea = 0.0;

        // 遍歷所有可能的三點組合 (i, j, k)，其中 i < j < k
        // 這是 O(N^3) 的時間複雜度，對於題目中最多 50 個點的限制是可接受的 (50^3 = 125,000)
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    // 計算由 points[i], points[j], points[k] 形成的三角形面積
                    double area = calculate(points[i], points[j], points[k]);
                    
                    // 更新最大面積
                    maxarea = max(maxarea, area);
                }
            }
        }

        return maxarea;
    }

private:
    double calculate(const vector<int>& p1, const vector<int>& p2, const vector<int>& p3) {
        // p1 = (x1, y1)
        double x1 = p1[0];
        double y1 = p1[1];
        // p2 = (x2, y2)
        double x2 = p2[0];
        double y2 = p2[1];
        // p3 = (x3, y3)
        double x3 = p3[0];
        double y3 = p3[1];

        // 計算向量 P1->P2 和 P1->P3 的二維向量
        // 外積結果的絕對值是兩向量所形成平行四邊形的面積
        // 三角形面積是平行四邊形面積的一半
        double cross_product = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
        
        return 0.5 * abs(cross_product);
    }

};

5. Test 範例

• 略

6. 相關題目與延伸概念

• 略

7. 補充：語法＆注意事項

沒辦法用極值點求，我本來想說兩層迴圈分別找x, y座標去求底跟高就好，但這個想法不正確，因此這題要以求三角形的數學方法下手。

極值法思路：

• 找 x 座標最大/最小的點
• 找 y 座標最大/最小的點
• 用這些點組成三角形

問題：
❌ 極值點可能共線（面積為0）
❌ 最大面積三角形可能完全不含極值點
❌ 不保證找到全局最佳解

ps. 部分內容經 AI 協助整理