力扣每日一题2022-05-15简单题：最大三角形面积

最大三角形面积

• • 题目描述
  • 思路
  • • 枚举
    • • Python实现
      • Java实现

---

题目描述

最大三角形面积

---

思路 枚举

枚举所有三角形，然后计算三角形的面积并找出最大的三角形面积。设三角形三个顶点的坐标为(x1, y1), (x2, y2), (x3, y3)，则三角形的面积为1/2*|x1y2+x2y3+x3y1-x1y3-x2y1-x3y2|

Python实现

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        def triangleArea(x1, y1, x2, y2, x3, y3):
            return abs(x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2) / 2
        return max(triangleArea(x1, y1, x2, y2, x3, y3) for (x1, y1), (x2, y2), (x3, y3) in combinations(points, 3))

Java实现

class Solution {
    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double ans = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j+1; k < n; k++) {
                    ans = Math.max(ans, triangleArea(points[i][0], points[i][1], points[j][0], points[j][1], points[k][0], points[k][1]));
                }
            }
        }
        return ans;
    }

    private double triangleArea(int x1, int y1, int x2, int y2, int x3, int y3) {
        return 0.5 * Math.abs(x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2);
    }
}