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

孤狼 · · 495 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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. 最大三角形面积

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

495 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传