Description

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:

1
2
3
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.
1
2
3
4
5
Constraints:

3 <= points.length <= 50
-50 <= xi, yi <= 50
All the given points are unique.

Anser

1
formula: $|x_1(y_2-y_3) + x_2(y_3-y_1) + x_3(y_1-y_2)|/2$

where $x_1, x_2, x_3$ are the x-coordinates of the three points, and $y_1, y_2, y_3$ are the y-coordinates of the three points.

Approach 1： bruteForce

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
26
27
28
29
30
31
class Solution {
    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double maxArea = 0.0;

        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = points[i][0];
            y[i] = points[i][1];
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    double area = Math.abs(
                        x[i] * (y[j] - y[k]) +
                        x[j] * (y[k] - y[i]) +
                        x[k] * (y[i] - y[j])
                    ) * 0.5;

                    if (area > maxArea) {
                        maxArea = area;
                    }
                }
            }
        }
        return maxArea;
    }
}

Approach 2： convexHull

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.*;

class Solution {
    public double largestTriangleArea(int[][] points) {
        if (points == null || points.length < 3) {
            return 0;
        }

        List<int[]> hull = convexHull(points);

        int h = hull.size();
        if (h < 3) return 0.0;

        double maxArea = 0.0;

        for (int i = 0; i < h; i++) {
            for (int j = i + 1; j < h; j++) {
                int k = (j + 1) % h;
                while (true) {
                    int nextK = (k + 1) % h;
                    double curArea = area(hull.get(i), hull.get(j), hull.get(k));
                    double nextArea = area(hull.get(i), hull.get(j), hull.get(nextK));
                    if (nextArea > curArea) {
                        k = nextK;
                    } else {
                        break;
                    }
                }
                maxArea = Math.max(maxArea, area(hull.get(i), hull.get(j), hull.get(k)));
            }
        }

        return maxArea;
    }

    private double area(int[] p1, int[] p2, int[] p3) {
        return 0.5 * Math.abs(
            p1[0] * (p2[1] - p3[1]) +
            p2[0] * (p3[1] - p1[1]) +
            p3[0] * (p1[1] - p2[1])
        );
    }

    private List<int[]> convexHull(int[][] points) {
        Arrays.sort(points, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

        List<int[]> lower = new ArrayList<>();
        for (int[] p : points) {
            while (lower.size() >= 2 && cross(lower.get(lower.size()-2), lower.get(lower.size()-1), p) <= 0) {
                lower.remove(lower.size()-1);
            }
            lower.add(p);
        }

        List<int[]> upper = new ArrayList<>();
        for (int i = points.length - 1; i >= 0; i--) {
            int[] p = points[i];
            while (upper.size() >= 2 && cross(upper.get(upper.size()-2), upper.get(upper.size()-1), p) <= 0) {
                upper.remove(upper.size()-1);
            }
            upper.add(p);
        }

        lower.remove(lower.size()-1);
        upper.remove(upper.size()-1);
        lower.addAll(upper);

        return lower;
    }

    private long cross(int[] o, int[] a, int[] b) {
        return (long)(a[0] - o[0]) * (b[1] - o[1]) - (long)(a[1] - o[1]) * (b[0] - o[0]);
    }
}