Thursday, April 12, 2018

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.
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.
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.

Analysis:

Solution:
class Solution {
    public double largestTriangleArea(int[][] points) {
        double area = 0.0;
        
        for (int p1 = 0; p1 < points.length; p1++) {
            for (int p2 = p1 + 1; p2 < points.length; p2++) {
                for (int p3 = p2 + 1; p3 < points.length; p3++) {
                    area = Math.max(area, getArea(points[p1], points[p2], points[p3]));
                }
            }
        }
        
        return area;
    }
    
    private double getArea(int[] p1, int[] p2, int[] p3) {
        return Math.abs((p2[0] - p1[0]) * (p3[1] - p1[1]) - 
                       0.5 * (p2[0] - p1[0]) * (p2[1] - p1[1]) - 
                       0.5 * (p3[0] - p1[0]) * (p3[1] - p1[1]) -
                       0.5 * (p2[0] - p3[0]) * (p3[1] - p2[1]));
    }
}



No comments:

Post a Comment