leetcode 812. Largest Triangle Area 最大三角形面积

Problem: 812. Largest Triangle Area 最大三角形面积

解题过程

三重循环的，计算三角形面积，需要用到海伦公式:p ( p − a ) ( p − b ) ( p − c ) \sqrt{p(p-a)(p-b)(p-c)}p(p−a)(p−b)(p−c)​，其中a,b,c分别是三角形的三条边长，p = a + b + c 2 p=\frac{a+b+c}{2}p=2a+b+c​，拿到最大值就行

Code

class Solution { public: double getArea(vector<int>& p1, vector<int>&p2) { double x1 = p1[0] - p2[0]; double y1 = p1[1] - p2[1]; return sqrt(x1 * x1 + y1 * y1); } double largestTriangleArea(vector<vector<int>>& points) { int n = points.size(); double d1, d2, d3, p, area, mx = 0; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { d1 = getArea(points[i], points[j]); for(int k = j + 1; k < n; k++) { d2 = getArea(points[i], points[k]); d3 = getArea(points[j], points[k]); p = (d1 + d2 + d3) / 2.0; area = sqrt(p * (p-d1) * (p-d2) * (p-d3)); if(mx < area) { mx = area; } } } } return mx; } };