题目
给定包含多个点的集合,从其中取三个点组成三角形,返回能组成的最大三角形的面积。
示例:
输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出: 2
解释:
这五个点如下图所示。组成的橙色三角形是最大的,面积为2。
注意:
3 <= points.length <= 50
.- 不存在重复的点。
-50 <= points[i][j] <= 50
.- 结果误差值在
10^-6
以内都认为是正确答案。
解题
方法一:模拟
思路
由图可得:$S\triangle{ABC}=S梯形{ABED}+S梯形{CBEF}-S梯形{ACFD}$
也就是:$S\triangle{ABC}=\lvert\frac{1}{2}(x_2-x_1)(y_1+y_2)+\frac{1}{2}(x_3-x_2)(y_2+y_3)-\frac{1}{2}(x_3-x_1)(y_1+y_3)\rvert$
代码
class Solution {
public double largestTriangleArea(int[][] points) {
int len = points.length;
double maxArea = 0;
for (int a = 0; a < len - 2; a++) {
for (int b = a + 1; b < len - 1; b++) {
for (int c = b + 1; c < len; c++) {
int x1 = points[a][0], y1 = points[a][1];
int x2 = points[b][0], y2 = points[b][1];
int x3 = points[c][0], y3 = points[c][1];
double leftArea = (x2 - x1) * (y1 + y2) / 2.0;
double rightArea = (x3 - x2) * (y2 + y3) / 2.0;
double bottomArea = (x3 - x1) * (y1 + y3) / 2.0;
maxArea = Math.max(maxArea, Math.abs(leftArea + rightArea - bottomArea));
}
}
}
return maxArea;
}
}
优化
化简计算后:
class Solution {
public double largestTriangleArea(int[][] points) {
int len = points.length;
double maxArea = 0;
for (int a = 0; a < len - 2; a++) {
for (int b = a + 1; b < len - 1; b++) {
for (int c = b + 1; c < len; c++) {
int x1 = points[a][0], y1 = points[a][1];
int x2 = points[b][0], y2 = points[b][1];
int x3 = points[c][0], y3 = points[c][1];
maxArea = Math.max(maxArea,
Math.abs(x1 * (y3-y2) + x2 * (y1-y3) + x3 * (y2-y1)) / 2.0);
}
}
}
return maxArea;
}
}
评论区