# Largest Triangle Area
**Difficulty:** EASY
[External](https://leetcode.com/problems/largest-triangle-area)
Canonical: https://scaleengineer.com/dsa/problems/largest-triangle-area
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array
---
## Problem
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:**

![](https://assets.glich.co/dsa/largest-triangle-area/image0.png) 

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

# Approaches
## Brute-Force Enumeration
This approach involves checking every possible triangle that can be formed by the given points. It uses three nested loops to select three distinct points, calculates the area of the triangle they form, and keeps track of the maximum area found so far. This method is straightforward to implement and guarantees finding the correct answer by exhaustive search.
**Time:** O(n^3), where n is the number of points. The three nested loops lead to a cubic number of iterations. · **Space:** O(1) extra space, as we only need a few variables to store the coordinates and the maximum area.
**Pros:** Very simple to understand and implement.; Requires no complex data structures or algorithms.; Sufficiently fast for the problem's constraints (n <= 50).
**Cons:** The time complexity of O(n^3) makes it inefficient for large datasets, although it's acceptable for the given constraints.
### Explanation
The algorithm iterates through every unique triplet of points `(i, j, k)` using three nested loops, where `i < j < k`. This ensures that each combination of three points is considered exactly once. For each triplet `points[i]`, `points[j]`, and `points[k]`, we calculate the area. The Shoelace formula is ideal for this, as it avoids complex trigonometric functions or square roots, relying only on the coordinates of the vertices. The formula is given by `Area = 0.5 * |x_i(y_j - y_k) + x_j(y_k - y_i) + x_k(y_i - y_j)|`. A running maximum `maxArea` is updated with the area of the current triangle if it's larger. Given the small constraint on the number of points (n <= 50), this cubic-time solution is perfectly feasible.

```java
class Solution {
    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double maxArea = 0.0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    int[] p1 = points[i];
                    int[] p2 = points[j];
                    int[] p3 = points[k];
                    
                    double area = 0.5 * Math.abs(p1[0] * (p2[1] - p3[1]) + 
                                                 p2[0] * (p3[1] - p1[1]) + 
                                                 p3[0] * (p1[1] - p2[1]));
                    
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
}
```
### Algorithm
- Initialize a variable `maxArea` to 0.0.
- Use three nested loops to iterate through all unique combinations of three points `(p1, p2, p3)` from the input array `points`.
- For each combination, calculate the area of the triangle formed by these three points. A common and efficient method is the Shoelace formula: `Area = 0.5 * |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2))|`.
- Compare the calculated `currentArea` with `maxArea` and update `maxArea` if `currentArea` is larger.
- After checking all possible triplets, `maxArea` will hold the area of the largest triangle.

## Convex Hull with Rotating Calipers
A more efficient, geometry-based approach relies on the fundamental property that the triangle with the largest area will have its vertices on the convex hull of the given points. This allows us to first reduce the problem to only the points on the hull and then use a specialized algorithm, known as 'rotating calipers', to find the largest triangle among these hull points in quadratic time.
**Time:** O(n^2). The convex hull calculation is O(n log n), and the rotating calipers algorithm on the `m` hull points is O(m^2). Since `m <= n`, the total complexity is O(n^2). · **Space:** O(n) to store the points on the convex hull.
**Pros:** Asymptotically faster with O(n^2) time complexity.; Much more scalable for larger numbers of points.
**Cons:** Significantly more complex to implement correctly.; Requires knowledge of computational geometry algorithms (Convex Hull, Rotating Calipers).; The performance gain is not critical for the given small constraints, making the implementation effort potentially unnecessary.
### Explanation
This advanced approach consists of two main parts. First, we compute the convex hull of the input points. The Monotone Chain algorithm is a standard choice, which sorts the points and builds the hull in O(n log n) time. Let the number of vertices on the hull be `m`.

Second, we find the largest-area triangle whose vertices are chosen from the `m` hull points. A brute-force O(m^3) check is possible, but the optimal 'rotating calipers' technique achieves this in O(m^2). The algorithm fixes a base of the triangle, say `(p_i, p_j)`, and efficiently finds the third vertex `p_k` that maximizes the triangle's area. The key insight is that as we 'rotate' the base by advancing `j` along the hull, the optimal third vertex `k` also moves monotonically. This avoids a full search for `k` for each new base, leading to the O(m^2) complexity.

The overall time complexity is O(n log n) for the hull computation plus O(m^2) for the rotating calipers part. Since `m <= n`, the total complexity is O(n^2).

```java
// Note: The following is a conceptual representation. A full implementation
// of Convex Hull and Rotating Calipers is non-trivial.
class Solution {
    // Helper to calculate area
    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]));
    }

    public double largestTriangleArea(int[][] points) {
        // Step 1: Compute the convex hull of the points.
        // This would be a call to a function like `getConvexHull(points)`,
        // which implements an algorithm like Monotone Chain (O(n log n)).
        List<int[]> hull = getConvexHull(points);

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

        double maxArea = 0.0;

        // Step 2: Use Rotating Calipers to find the largest triangle on the hull (O(m^2)).
        for (int i = 0; i < m; i++) {
            int k = (i + 2) % m;
            for (int j = i + 1; j < m; j++) {
                int[] p_i = hull.get(i);
                int[] p_j = hull.get(j);
                
                // Find the farthest point k for the base (i, j).
                // The optimal k moves monotonically as j advances.
                while (true) {
                    int next_k = (k + 1) % m;
                    if (area(p_i, p_j, hull.get(next_k)) > area(p_i, p_j, hull.get(k))) {
                        k = next_k;
                    } else {
                        break;
                    }
                }
                maxArea = Math.max(maxArea, area(p_i, p_j, hull.get(k)));
            }
        }
        return maxArea;
    }

    // A full implementation of a convex hull algorithm (e.g., Monotone Chain)
    // would be required here. It's omitted for brevity.
    private List<int[]> getConvexHull(int[][] points) {
        // ... O(n log n) implementation ...
        // Returns a list of points on the hull in counter-clockwise order.
        // For this example, we'll just use all points to make it runnable,
        // though this defeats the purpose of the optimization.
        Arrays.sort(points, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        List<int[]> hull = new ArrayList<>();
        // Lower hull
        for (int[] p : points) {
            while (hull.size() >= 2 && crossProduct(hull.get(hull.size() - 2), hull.get(hull.size() - 1), p) <= 0) {
                hull.remove(hull.size() - 1);
            }
            hull.add(p);
        }
        // Upper hull
        int lowerHullSize = hull.size();
        for (int i = points.length - 2; i >= 0; i--) {
            int[] p = points[i];
            while (hull.size() > lowerHullSize && crossProduct(hull.get(hull.size() - 2), hull.get(hull.size() - 1), p) <= 0) {
                hull.remove(hull.size() - 1);
            }
            hull.add(p);
        }
        hull.remove(hull.size() - 1); // Remove duplicate start point
        return hull;
    }

    private int crossProduct(int[] p1, int[] p2, int[] p3) {
        return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]);
    }
}
```
### Algorithm
- **Step 1: Compute the Convex Hull.** First, find the convex hull of the set of `n` points. An efficient algorithm like the Monotone Chain (takes O(n log n)) can be used. This gives a smaller set of `m` points (`m <= n`) that form the vertices of the convex hull.
- **Step 2: Find the Largest Triangle on the Hull.** The largest triangle must have its vertices on the convex hull. Instead of a naive O(m^3) check on the hull points, use the 'Rotating Calipers' algorithm, which finds the largest triangle in a convex polygon in O(m^2) time.
- The rotating calipers algorithm works by fixing one vertex `i` and one side `(i, j)` of the hull. It then finds the third vertex `k` that is farthest from the line segment `(i, j)`. As `j` advances around the hull, the optimal `k` also advances monotonically, allowing for an efficient O(m) scan for a fixed `i`.
- By iterating `i` over all `m` vertices, the total time for this step is O(m^2).

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```