Leetcode题解
Search…
812.Largest Triangle Area
812.Largest Triangle Area
难度:Easy
给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。
1
示例:
2
输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
3
输出: 2
4
解释:
5
这五个点如下图所示。组成的橙色三角形是最大的，面积为2
Copied!
注意:
1
3 <= points.length <= 50.
2
不存在重复的点。
3
-50 <= points[i][j] <= 50.
4
结果误差值在 10^-6 以内都认为是正确答案。
Copied!
数量不多,直接海伦公式求面积:
1
class Solution {
2
private:
3
double area(vector<int>a, vector<int> b, vector<int> c)
4
{
5
double lab, lbc,lac;
6
// cout<< a[0] <<a[1]<<endl;
7
// cout<<b[0]<<b[1]<<endl;
8
//cout<< c[0]<<c[1]<<endl;
9
lab=sqrt((a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]));
10
lbc=sqrt((c[0]-b[0])*(c[0]-b[0]) + (c[1]-b[1])*(c[1]-b[1]));
11
lac=sqrt((a[0]-c[0])*(a[0]-c[0]) + (a[1]-c[1])*(a[1]-c[1]));
12
// cout<< lab << ", "<<lbc << ", "<<lac <<endl;
13
double s=(lab+lbc+lac)/2;
14
return sqrt(s*(s-lab)*(s-lbc)*(s-lac));
15
16
}
17
public:
18
double largestTriangleArea(vector<vector<int>>& points) {
19
double sum=0.0;
20
for(int i=0;i<points.size();i++)
21
for(int j=i+1;j<points.size();j++)
22
for(int k=j+1;k<points.size();k++)
23
{
24
sum=max(sum, area(points[i], points[j], points[k]));
25
// cout<<sum<<endl;
26
}
27
return sum;
28
}
29
};
Copied!
Last modified 5mo ago
Copy link