Algorithm
Problem Name: 812. Largest Triangle Area
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:
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.
Example 2:
Input: points = [[1,0],[0,0],[0,1]] Output: 0.50000
Constraints:
3 <= points.length <= 50-50 <= xi, yi <= 50- All the given points are unique.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public double largestTriangleArea(int[][] points) {
int n = points.length;
double maxArea = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
maxArea = Math.max(maxArea, getArea(points[i], points[j], points[k]));
}
}
}
return maxArea;
}
private double getArea(int[] P, int[] Q, int[] R) {
return 0.5 * Math.abs(P[0] * Q[1] + Q[0] * R[1] + R[0] * P[1]
-P[1] * Q[0] - Q[1] * R[0] - R[1] * P[0]);
}
}
Input
points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output
2.00000
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const largestTriangleArea = function(points) {
const N = points.length
let ans = 0
for(let i = 0; i < N; i++) {
for(let j = i + 1; j < N; j++) {
for(let k = j + 1; k < N; k++) {
ans = Math.max(ans, area(points[i], points[j], points[k]))
}
}
}
return ans
};
function area(P,Q,R) {
return 0.5 * Math.abs(P[0]*Q[1] + Q[0]*R[1] + R[0]*P[1] -P[1]*Q[0] - Q[1]*R[0] - R[1]*P[0])
}
Input
points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output
2.00000
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def largestTriangleArea(self, p):
"""
:type points: List[List[int]]
:rtype: float
"""
from itertools import combinations as cb
def f(p1, p2, p3):
(x1, y1), (x2, y2), (x3, y3) = p1,p2,p3
return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)
return max(f(a, b, c) for a, b, c in cb(p, 3))
Input
points = [[1,0],[0,0],[0,1]]
Output
0.50000
#4 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0812_LargestTriangleArea
{
public double LargestTriangleArea(int[][] points)
{
int N = points.Length;
double ans = 0;
for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j)
for (int k = j + 1; k < N; ++k)
ans = Math.Max(ans, Area(points[i], points[j], points[k]));
return ans;
}
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]);
}
}
}
Input
points = [[1,0],[0,0],[0,1]]
Output
0.50000