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:
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.
Solutions
Solution: Enumerate Triangle Area Formula
Given three points (x_1, y_1), (x_2, y_2), (x_3, y_3) on a plane, the area formula is:
$S = 1⁄2 | x_1y_2 + x_2y_3 + x_3y_1 - x_1y_3 - x_2y_1 - x_3y_2 |$
We can enumerate all combinations of three points and calculate the maximum area.
The time complexity is O(n^3), where n is the number of points. The space complexity is O(1).
PythonJavaC++GoTypeScriptRust
class Solution:
def largestTriangleArea(self, points: List[List[int]]) -> float:
ans = 0
for x1, y1 in points:
for x2, y2 in points:
for x3, y3 in points:
u1, v1 = x2 - x1, y2 - y1
u2, v2 = x3 - x1, y3 - y1
t = abs(u1 * v2 - u2 * v1) / 2
ans = max(ans, t)
return ans(code-box)
class Solution {
public double largestTriangleArea(int[][] points) {
double ans = 0;
for (int[] p1 : points) {
int x1 = p1[0], y1 = p1[1];
for (int[] p2 : points) {
int x2 = p2[0], y2 = p2[1];
for (int[] p3 : points) {
int x3 = p3[0], y3 = p3[1];
int u1 = x2 - x1, v1 = y2 - y1;
int u2 = x3 - x1, v2 = y3 - y1;
double t = Math.abs(u1 * v2 - u2 * v1) / 2.0;
ans = Math.max(ans, t);
}
}
}
return ans;
}
}(code-box)
class Solution {
public:
double largestTriangleArea(vector<vector<int>>& points) {
double ans = 0;
for (auto& p1 : points) {
int x1 = p1[0], y1 = p1[1];
for (auto& p2 : points) {
int x2 = p2[0], y2 = p2[1];
for (auto& p3 : points) {
int x3 = p3[0], y3 = p3[1];
int u1 = x2 - x1, v1 = y2 - y1;
int u2 = x3 - x1, v2 = y3 - y1;
double t = abs(u1 * v2 - u2 * v1) / 2.0;
ans = max(ans, t);
}
}
}
return ans;
}
};(code-box)
func largestTriangleArea(points [][]int) float64 {
ans := 0.0
for _, p1 := range points {
x1, y1 := p1[0], p1[1]
for _, p2 := range points {
x2, y2 := p2[0], p2[1]
for _, p3 := range points {
x3, y3 := p3[0], p3[1]
u1, v1 := x2-x1, y2-y1
u2, v2 := x3-x1, y3-y1
t := float64(abs(u1*v2-u2*v1)) / 2.0
ans = math.Max(ans, t)
}
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}(code-box)
function largestTriangleArea(points: number[][]): number {
let ans = 0;
for (const [x1, y1] of points) {
for (const [x2, y2] of points) {
for (const [x3, y3] of points) {
const u1 = x2 - x1,
v1 = y2 - y1;
const u2 = x3 - x1,
v2 = y3 - y1;
const t = Math.abs(u1 * v2 - u2 * v1) / 2;
ans = Math.max(ans, t);
}
}
}
return ans;
}(code-box)
impl Solution {
pub fn largest_triangle_area(points: Vec<Vec<i32>>) -> f64 {
let mut ans: f64 = 0.0;
for point1 in &points {
let (x1, y1) = (point1[0], point1[1]);
for point2 in &points {
let (x2, y2) = (point2[0], point2[1]);
for point3 in &points {
let (x3, y3) = (point3[0], point3[1]);
let u1 = x2 - x1;
let v1 = y2 - y1;
let u2 = x3 - x1;
let v2 = y3 - y1;
let t = ((u1 * v2 - u2 * v1) as f64).abs() / 2.0;
ans = ans.max(t);
}
}
}
ans
}
}(code-box)
