812. 最大三角形面积)( 向量叉积求三角形面积 + 三阶行列式求面积(枚举) )

812. 最大三角形面积)( 向量叉积求三角形面积 + 三阶行列式求面积(枚举) ),第1张

文章目录
  • Question
  • Ideas
    • 1、Answer( Java ) - 向量叉积求三角形面积
      • Code
    • 2、Answer( Java ) - 三阶行列式求面积(枚举)
      • Code

Question

812. 最大三角形面积

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/largest-triangle-area/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

Ideas 1、Answer( Java ) - 向量叉积求三角形面积

解法思路:向量叉积求三角形面积

👍设向量Oa(x1,y1) Ob(x2,y2)平面叉积的坐标公式求解平行四边形面积为:S=|x1*y2 - x2*y1| (注意需要取 绝对值

故三角形面积即为平行四边形面积的一半

Code
/**
 * @author Listen 1024
 * @description  812. 最大三角形面积)( 向量叉积求三角形面积 + 三阶行列式求面积(枚举) )
 * 时间复杂度 O(n^3)  其中 n 是数组 points 的长度
 * 空间复杂度 O(1)
 * @date 2022-05-15 8:22
 */
class Solution {
    public double largestTriangleArea(int[][] points) {
        double res = 0;
        for (int[] p1 : points) {
            for (int[] p2 : points) {
                for (int[] p3 : points) {
                    double x1 = p1[0];
                    double x2 = p2[0] - x1;
                    double x3 = p3[0] - x1;
                    double y1 = p1[1];
                    double y2 = p2[1] - y1;
                    double y3 = p3[1] - y1;
                    double s = Math.abs(x2 * y3 - x3 * y2) / 2;
                    res = Math.max(res, s);
                }
            }
        }
        return res;
    }
}
2、Answer( Java ) - 三阶行列式求面积(枚举)

解法思路:三阶行列式求面积(枚举)

👍三角形面积 S 可以用行列式的绝对值表示

Code
/**
 * @author Listen 1024
 * @description  812. 最大三角形面积)( 向量叉积求三角形面积 + 三阶行列式求面积(枚举) )
 * 时间复杂度 O(n^3)  其中 n 是数组 points 的长度
 * 空间复杂度 O(1)
 * @date 2022-05-15 8:22
 */
class Solution {
    public double largestTriangleArea(int[][] points) {
        double res = 0;
        int len = points.length;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                for (int k = j + 1; k < len; k++) {
                    double triangleArea = 0.5 * Math.abs(points[i][0] * points[j][1] + points[j][0] * points[k][1] + points[k][0] * points[i][1] - points[i][0] * points[k][1] - points[j][0] * points[i][1] - points[k][0] * points[j][1]);
                    res = Math.max(res, triangleArea);
                }
            }
        }
        return res;
    }
}
//部分题解参考链接(如侵删)
https://leetcode.cn/problems/largest-triangle-area/solution/zui-da-san-jiao-xing-mian-ji-by-leetcode-yefh/

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/921310.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-16
下一篇 2022-05-16

发表评论

登录后才能评论

评论列表(0条)

保存