Largest Triangle Area
Given an array of points on the X-Y plane points where points[i] = [xi, yi], return the area of the largest triangle that can be formed by any three different points. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2.00000
Explanation: The five points are shown in the above figure. The red triangle is the largest.
Example 2:
Input: points = [[1,0],[0,0],[0,1]]
Output: 0.50000
Constraints:
3 <= points.length <= 50
-50 <= xi, yi <= 50
All the given points are unique.
思路一：海伦公式直接计算
public double largestTriangleArea(int[][] points) {
double maxArea = 0;
for (int i = 0; i < points.length; i++) {
for (int j = i + 1; j < points.length; j++) {
for (int k = j + 1; k < points.length; k++) {
maxArea = Math.max(maxArea, Heron(points[i], points[j], points[k]));
}
}
}
return maxArea;
}
public double Heron(int[] p1, int[] p2, int[] p3) {
double a = Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2));
double b = Math.sqrt(Math.pow(p1[0] - p3[0], 2) + Math.pow(p1[1] - p3[1], 2));
double c = Math.sqrt(Math.pow(p2[0] - p3[0], 2) + Math.pow(p2[1] - p3[1], 2));
if (a + b <= c || a + c <= b || b + c <= a) {
return 0;
}
double p = (a + b + c) / 2;
return Math.sqrt(p * (p - a) * (p - b) * (p - c));
}