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

文章目录

• 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/