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

812. 最大三角形面积

问题描述

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

示例

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

image-20200305134615400.png

问题分析

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

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

向量(也称欧几里得向量、几何向量、矢量)

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

已知坐标点求向量

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

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

image-20200305142347134.png

所以三个坐标点构成三角形的面积为|(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
}

总结

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

本文来自:Segmentfault

感谢作者:孤狼

查看原文:力扣算法学习个人分享812. 最大三角形面积

• 编辑
• 预览