侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【模拟】最大三角形面积

GabrielxD
2022-05-16 / 0 评论 / 0 点赞 / 460 阅读 / 413 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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 以内都认为是正确答案。

解题

方法一:模拟

思路

image-20220516135413886

由图可得:$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;
    }
}
0

评论区