最大三角形面积Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。
示例: 输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]] 输出: 2 解释: 这五个点如下图所示。组成的橙色三角形是最大的，面积为2。
注意:
- 3 <= points.length <= 50.
- 不存在重复的点。
- -50 <= points[i][j] <= 50.
- 结果误差值在 10^-6 以内都认为是正确答案。
# 思路
// 枚举 + 数学 向量叉积
//三个点构成两个共起点的向量。
//两个向量可作平行四边形，面积是它们构成的行列式值的绝对值。
//三角形面积是平行四边形面积的一半。
//不需要回头：如果某个点p1曾被选中作为起点，那么在p2作为起点时，不需要考虑p1作为终点的情况。
//理由：设第三个点p3,向量p1p2、p1p3构成的三角形和向量p2p1、p2p3构成的三角形是同一个。
# 解法
class Solution {
// 枚举 + 数学 向量叉积
public double largestTriangleArea(int[][] points) {
int n = points.length;
double res = 0;
for (int i = 0 ; i < n - 2 ; i++){
int a[] = points[i];
for (int j = i + 1; j < n - 1 ; j++){
int b[] = points[j];
for (int k = j + 1 ; k < n ; k++){
int c[] = points[k];
int xAB = b[0] - a[0];
int yAB = b[1] - a[1];
int xAC = c[0] - a[0];
int yAC = c[1] - a[1];
if (Math.abs(xAB * yAC - xAC * yAB) / 2.0 > res)
res =Math.abs(xAB * yAC - xAC * yAB)/ 2.0;
}
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 总结
- 分析出几种情况，然后分别对各个情况实现
