Leetcode笔记 每日一题 812 最大三角形面积

Leetcode笔记 每日一题 812 最大三角形面积(22.05.15)

Leetcode 每日一题 812 最大三角形面积(22.05.15)

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

输入: 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 = ( 1 / 2 ) ∗ ( x 1 y 2 + x 2 y 3 + x 3 y 1 − x 1 y 3 − x 2 y 1 − x 3 y 2 ) S= (1/2)* (x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2) S=(1/2)∗(x1​y2​+x2​y3​+x3​y1​−x1​y3​−x2​y1​−x3​y2​)
• 方法：遍历读取points中的元素,x、y、z分别表示 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​)、 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​)、 ( x 3 , y 3 ) (x_3,y_3) (x3​,y3​)
• 最后根据公式计算面积并求最大值

Python代码

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        n = len(points)
        res = []
        for a in range(n-2):
            x = points[a]
            for b in range(a+1,n-1):
                y = points[b]
                for c in range(a+2,n):
                    z = points[c]
                    s = 0.5*abs(x[0]*y[1] + y[0]*z[1] + z[0]*x[1] - x[0]*z[1] - y[0]*x[1] - z[0]*y[1])
                    res.append(s)
        return max(res)

或者可以用itertools函数中的combinations排列组合points元素，代码如下：

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        ans = []
        for x,y,z in itertools.combinations(points,3):
            s = 0.5*abs(x[0]*y[1] + y[0]*z[1] + z[0]*x[1] - x[0]*z[1] - y[0]*x[1] - z[0]*y[1])
            ans.append(s)
        return max(ans)