題意：給你一堆點赴精，選出三個點來組成三角形面積最大息尺，輸出最大三角形的面積。
解題思路：開始想著用圖論的方法找到這三個點嵌戈，無奈陷入江局覆积，看了數(shù)據(jù)規(guī)模共50個點，使用暴力算法的時間復(fù)雜度是O（n3）熟呛，可以接受宽档。
已知三個點坐標(biāo)求三角形面積公式有兩種較為簡單的方法，一種是海倫公式惰拱，s=sqrt(p(p-a)(p-b)(p-c))雌贱，其中p=(1/2)(a+b+c)，其中a偿短、b、c分別是三個邊的長度馋没。通過點計算邊昔逗，然后計算面積。
image.png
image.png
所以三角形的面積S= (1/2) * abs
|x1 y1 1|
|x2 y2 1|
|x3 y3 1|
class Solution {
public:
double largestTriangleArea(vector<vector<int>>& points) {
double s, ans = 0;
for(int i = 0; i < points.size() - 2; i++)
{
for(int j = i + 1; j < points.size()-1; j++)
{
for(int k = j + 1; k < points.size(); k++)
{
s = (1.0/2) * abs(points[i][0]*points[j][1] + points[j][0]*points[k][1]
+ points[i][1]*points[k][0] - points[k][0]*points[j][1]
- points[j][0]*points[i][1]-points[i][0]*points[k][1]);
ans = ans > s ? ans : s;
}
}
}
return ans;
}
};
