812.Largest Triangle Area

812.Largest Triangle Area

难度:Easy

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

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

注意:

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

数量不多,直接海伦公式求面积:

class Solution {
private:
double area(vector<int>a, vector<int> b, vector<int> c)
{
double lab, lbc,lac;
// cout<< a[0] <<a[1]<<endl;
// cout<<b[0]<<b[1]<<endl;
//cout<< c[0]<<c[1]<<endl;
lab=sqrt((a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]));
lbc=sqrt((c[0]-b[0])*(c[0]-b[0]) + (c[1]-b[1])*(c[1]-b[1]));
lac=sqrt((a[0]-c[0])*(a[0]-c[0]) + (a[1]-c[1])*(a[1]-c[1]));
// cout<< lab << ", "<<lbc << ", "<<lac <<endl;
double s=(lab+lbc+lac)/2;
return sqrt(s*(s-lab)*(s-lbc)*(s-lac));
}
public:
double largestTriangleArea(vector<vector<int>>& points) {
double sum=0.0;
for(int i=0;i<points.size();i++)
for(int j=i+1;j<points.size();j++)
for(int k=j+1;k<points.size();k++)
{
sum=max(sum, area(points[i], points[j], points[k]));
// cout<<sum<<endl;
}
return sum;
}
};