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;
    }
};

Last updated