【模拟】最大三角形面积

题目

812. 最大三角形面积

---

给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。

示例:
输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出: 2
解释: 
这五个点如下图所示。组成的橙色三角形是最大的，面积为2。

注意:

• 3 <= points.length <= 50.
• 不存在重复的点。
• -50 <= points[i][j] <= 50.
• 结果误差值在 10^-6 以内都认为是正确答案。

解题

方法一：模拟

思路

由图可得：$S\triangle{ABC}=S梯形{ABED}+S梯形{CBEF}-S梯形{ACFD}$

也就是：$S\triangle{ABC}=\lvert\frac{1}{2}(x_2-x_1)(y_1+y_2)+\frac{1}{2}(x_3-x_2)(y_2+y_3)-\frac{1}{2}(x_3-x_1)(y_1+y_3)\rvert$

代码

class Solution {
    public double largestTriangleArea(int[][] points) {
        int len = points.length;
        double maxArea = 0;
        for (int a = 0; a < len - 2; a++) {
            for (int b = a + 1; b < len - 1; b++) {
                for (int c = b + 1; c < len; c++) {
                    int x1 = points[a][0], y1 = points[a][1];
                    int x2 = points[b][0], y2 = points[b][1];
                    int x3 = points[c][0], y3 = points[c][1];
                    double leftArea = (x2 - x1) * (y1 + y2) / 2.0;
                    double rightArea = (x3 - x2) * (y2 + y3) / 2.0;
                    double bottomArea = (x3 - x1) * (y1 + y3) / 2.0;
                    maxArea = Math.max(maxArea, Math.abs(leftArea + rightArea - bottomArea));
                }
            }
        }
        return maxArea;
    }
}

优化

化简计算后：

class Solution {
    public double largestTriangleArea(int[][] points) {
        int len = points.length;
        double maxArea = 0;
        for (int a = 0; a < len - 2; a++) {
            for (int b = a + 1; b < len - 1; b++) {
                for (int c = b + 1; c < len; c++) {
                    int x1 = points[a][0], y1 = points[a][1];
                    int x2 = points[b][0], y2 = points[b][1];
                    int x3 = points[c][0], y3 = points[c][1];
                    maxArea = Math.max(maxArea, 
                        Math.abs(x1 * (y3-y2) + x2 * (y1-y3) + x3 * (y2-y1)) / 2.0);
                }
            }
        }
        return maxArea;
    }
}