最大三角形面积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

# 总结

分析出几种情况，然后分别对各个情况实现