leetcode-812-Largest-Triangle-Area

发表于   |  

描述

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.

1
2
3
4
5
Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation: 
The five points are show in the figure below. The red triangle is the largest.

img

Notes:

  • 3 <= points.length <= 50.
  • No points will be duplicated.
  • -50 <= points[i][j] <= 50.
  • Answers within 10^-6 of the true value will be accepted as correct.

分析

给定一些二维数组中的节点，求这些节点能够组成的三角形的最大面积。求三角形面积可以用 Shoelace formula 解决（原来叫做鞋带公式）。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public double largestTriangleArea(int[][] points) {
        int N = points.length;
        double result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                for (int k = j+1; k < N; k++) {
                    result = Math.max(result, area(points[i], points[j], points[k]));
                }
            }
        }
        return result;
    }
    
    private double area(int[] A, int[] B, int[] C) {
        return 0.5 * Math.abs(A[0]*B[1] + B[0]*C[1] + C[0]*A[1] - A[1]*B[0] - B[1]*C[0] - C[1]*A[0]);
    }
}

题目来源