LeetCode每日一题——812. 最大三角形面积

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

题目

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

示例

示例:

输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]

输出: 2

解释: 这五个点如下图所示。组成的橙色三角形是最大的,面积为2。

2345_image_file_copy_4.jpg

注意:

3 <= points.length <= 50.

不存在重复的点。

-50 <= points[i][j] <= 50.

结果误差值在 10^-6 以内都认为是正确答案。

思路

由于数据量较小,我们可以通过三角形的三个顶点穷举所有三角形,并求出三角形面积,最终取最大值

补充

设三角形三个顶点的坐标为 (x1, y1),(x2, y2),(x3, y3),则三角形面积 S 可以用行列式的绝对值表示:

2345_image_file_copy_5.jpg

S= (1/2) |x1y2+x2y3+x3y1-x1y3-x2y1-x3y2|

题解

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        def triangleArea(x1: int, y1: int, x2: int, y2: int, x3: int, y3: int) -> float:
            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))
目录
相关文章
|
6月前
|
存储
leetcode2975. 移除栅栏得到的正方形田地的最大面积
leetcode2975. 移除栅栏得到的正方形田地的最大面积
43 1
|
6月前
|
算法 vr&ar 图形学
☆打卡算法☆LeetCode 223. 矩形面积 算法解析
☆打卡算法☆LeetCode 223. 矩形面积 算法解析
LeetCode 223. 矩形面积
LeetCode 223. 矩形面积
66 0
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
50 6
|
3月前
|
Python
【Leetcode刷题Python】120. 三角形最小路径和
LeetCode 120题 "三角形最小路径和" 的Python实现,使用动态规划算法找出从三角形顶部到底部的最小路径和。
21 0
|
3月前
|
Python
【Leetcode刷题Python】611. 有效三角形的个数
提供了解决LeetCode "有效三角形的个数" 问题的Python实现代码。
17 0
|
5月前
【LeetCode刷题】有效三角形个数、查找总价值为目标值的两个商品
【LeetCode刷题】有效三角形个数、查找总价值为目标值的两个商品
|
5月前
|
存储 算法 数据可视化
LeetCode 题目 120:三角形最小路径和
LeetCode 题目 120:三角形最小路径和
|
6月前
|
算法
【优选算法】——Leetcode——611. 有效三角形的个数
【优选算法】——Leetcode——611. 有效三角形的个数