leetcode 812. 最大三角形面积

题目描述

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

示例:
输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出: 2

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

注意:

  1. 3 <= points.length <= 50.
  2. 不存在重复的点。
  3. -50 <= points[i][j] <= 50.
  4. 结果误差值在 10^-6 以内都认为是正确答案。

题解

通过三点可以计算出三角形的面积,area = (x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2)) / 2

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func largestTriangleArea(points [][]int) float64 {
res := 0.0
for i := 0; i < len(points)-2; i++ {
for j := i+1; j < len(points)-1; j++ {
for k := j+1; k < len(points); k++ {
area := computeArea(points[i], points[j], points[k])
if area > res {
res = area
}
}
}
}
return res
}

func computeArea(a, b, c []int) float64 {
area := a[0]*(b[1]-c[1]) + b[0]*(c[1]-a[1]) + c[0]*(a[1]-b[1])
if area < 0 {
area = -area
}
return float64(area) / 2.0
}