题目描述：

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

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

注意:

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

解题思路一：已知三角形的三边长分别为a、b、c，根据海伦公式则三角形的面积公式如下图所示，其中公式里的p为半周长：

到这里想必大家都会求了吧。代码如下

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        int n = points.size();
        double a,b,c,p,ans=0.0,s;
        for(int i=0;i<n;++i)
            for(int j=1;j<n;++j)
                for(int k=2;k<n;++k){
                    a=sqrt(pow((points[i][0]-points[j][0]),2)+pow(points[i][1]-points[j][1],2));
                    b=sqrt(pow((points[i][0]-points[k][0]),2)+pow(points[i][1]-points[k][1],2));
                    c=sqrt(pow((points[k][0]-points[j][0]),2)+pow(points[k][1]-points[j][1],2));
                    p=(a+b+c)/2;
                    s=sqrt(p*(p-a)*(p-b)*(p-c));
                    ans=max(ans,s);
                }
        return ans;        
    }
};

复杂度分析

时间复杂度：O(n³)，其中 nn 是数组points 的长度。三重循环需要 O(n³)。

空间复杂度：O(1)。