812. 最大三角形面积

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

示例:
输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出: 2
解释:
这五个点如下图所示。组成的橙色三角形是最大的,面积为2。

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

题解

三层遍历 海伦公式:

已知三角形三边a,b,c,则(海伦公式)(p=(a+b+c)/2)S=sqrt[p(p-a)(p-b)(p-c)]

/**
 * @param {number[][]} points
 * @return {number}
 */
var largestTriangleArea = function(points) {
    let res = 0
    for (let i = 0; i < points.length - 2; i++) {
        for (let j = i + 1; j < points.length - 1; j++) {
            for (let k = j + 1; k < points.length; k++) {
                let a = Math.sqrt(Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2))
                let b = Math.sqrt(Math.pow(points[k][0] - points[j][0], 2) + Math.pow(points[k][1] - points[j][1], 2))
                let c = Math.sqrt(Math.pow(points[i][0] - points[k][0], 2) + Math.pow(points[i][1] - points[k][1], 2))
                let p = (a + b + c) / 2
                res = Math.max(res, isNaN(Math.sqrt(p * (p - a) * (p - b) * (p - c))) ? 0 : Math.sqrt(p * (p - a) * (p - b) * (p - c)))
            }
        }
    }
    return res
};

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注