力扣算法学习个人分享812. 最大三角形面积

812. 最大三角形面积

问题描述

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

示例

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

问题分析

在平面直角坐标系中，只要三个坐标点不在同一直线上就可构成三角形。

• 当三个坐标点在同一直线上时，面积为零。
• 当三个坐标点不在同一直线上，求三个坐标点构成的三角形面积最简单的方式是使用向量。

向量（也称欧几里得向量、几何向量、矢量）

• 指具有大小和方向的量。它可以形象的表示为带箭头的线段。箭头所指代表向量的方向；线段长度代表向量的大小。

已知坐标点求向量

设A(x1,y1),B(x2,y2)，C(x3,y3)
AB=(x2-x1,y2-y1),AC=(x3-x1,y3-y1), AB、AC表示向量

向量求三角形面积公式推导

所以三个坐标点构成三角形的面积为|(x2-x1)(y3-y1)-(x3-x1)(y2-y1)|/2

我的代码

func largestTriangleArea(points [][]int) float64 {
    area := float64(0)
    for i := 0; i< len(points)-2; i++ {
        for j := 1; j < len(points)-1; j++ {
            for k := 2; k <len(points); k++ {
                if num := CalculateArea(points[i],points[j],points[k]); num  > area {
                    area = num
                }
            }
        }

    }
    return area
}
//计算面积
func CalculateArea(a ,b ,c []int)  float64{
    AB := []float64{float64(a[1]-b[1]),float64(a[0]-b[0])}
    AC := []float64{float64(a[1]-c[1]),float64(a[0]-c[0])}
    Area := math.Abs(AB[1]*AC[0]-AB[0]*AC[1])/2
    return Area
}

总结

个人感觉我用穷举法列出所有坐标的组合的方法不是很好，自己没有想到更好的方式，如果哪位大佬有更好的方式请指教小弟一下。

有疑问加站长微信联系（非本文作者）