Created time
May 16, 2022 05:33 AM
date
status
category
Origin
summary
tags
type
URL
icon
password
slug
最大三角形面积
给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。不存在重复的点。结果误差值在
10^-6 以内都认为是正确答案。相关标签：几何, 数组, 数学。Largest Triangle Area
Given an array of points on the X-Y plane
points where points[i] = [xi, yi], return the area of the largest triangle that can be formed by any three different points. Answers within 10^(-5) of the actual answer will be accepted. All the given points are unique. Related Topics: Array, Math, Geometry.最大三角形的面积，其实求三角形的面积有很多种方法，那么在计算机里面一般比较常用的是叉积，就是我们高中学的叉积。如何求一个三角形的面积呢？比如一个三角形的两个点,那么这个三角形的有向面积应该是两个向量的叉积。叉积公式还记得嘛？就是。这个面积是有向面积，就是如果说我们第二个点在第一个点的逆时针方向，那么这个面积是正的，否则这个面积是负的。
那么这题的话我们直接去枚举就可以了。它是给我们很多点然后求由这很多个点构成的三角形的面积的最大值。我们可以随便遍历一下所有三个点的组合，所有三个点的组合，然后我们求面积的时候其实就是求一下c这个点减去a这个点得到的向量叉乘上b这个点减去a这个点得到的向量，也就是说我们其实求的是ac和ab两个向量围成的面积，最后注意要取绝对值就可以了。
用叉积来求的话大家会发现算法的精度更高一点，当然也可以用海伦公式，海伦公式也是可以用的，但是海伦公式的话大家可以发现会有开根号的一个操作，那么开根号的操作精度就会稍微低一些，所以一般计算机里面用的比较多的还是叉积公式，叉积公式不涉及到开根号只涉及到了乘法和减法，运算量是比较小的。所以它是一个精度非常高而且运行效率比较快的一个算法。叉积其实是计算几何的一个用的比较多的非常基本的概念。
复杂度分析：时间复杂度,其中是数组的长度。三重循环需要。空间复杂度。
然后我们来看一下代码怎么写：