# LeetCode 812: Largest Triangle Area

## Problem Restatement

We are given an array of unique points on the X-Y plane.

Each point is written as:

```python
[x, y]
```

We need to choose any three different points and form a triangle.

Return the largest possible triangle area.

Answers within `10^-5` of the actual answer are accepted. The constraints are small: `3 <= points.length <= 50`, and each coordinate is between `-50` and `50`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of 2D points |
| Output | The largest triangle area |
| Point format | `[x, y]` |
| Required choice | Three different points |
| Accepted error | `10^-5` |

## Examples

Example 1:

```python
points = [[0, 0], [0, 1], [1, 0], [0, 2], [2, 0]]
```

The largest triangle can be formed by:

```python
[0, 0], [0, 2], [2, 0]
```

This is a right triangle with base `2` and height `2`, so its area is:

```python
2.0
```

The answer is:

```python
2.00000
```

Example 2:

```python
points = [[1, 0], [0, 0], [0, 1]]
```

These three points form a right triangle with base `1` and height `1`.

The area is:

```python
0.5
```

The answer is:

```python
0.50000
```

## First Thought: Check Every Triangle

There are at most `50` points.

The number of ways to choose three points is:

```python
C(50, 3) = 19600
```

That is small enough.

So we can enumerate every triplet of points, compute its area, and keep the maximum.

## Key Insight

We do not need distances, angles, or square roots.

For three points:

```python
A = (x1, y1)
B = (x2, y2)
C = (x3, y3)
```

The area of the triangle is half the absolute value of the 2D cross product:

```python
abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) / 2
```

The cross product gives the signed area of the parallelogram formed by vectors `AB` and `AC`. A triangle is half of that parallelogram.

If the three points are collinear, the cross product is `0`, so the area is `0`.

## Algorithm

Initialize:

```python
best = 0.0
```

Loop over all triplets of points:

```python
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
```

For each triplet:

1. Let the points be `A`, `B`, and `C`.
2. Compute the triangle area using the cross product formula.
3. Update `best` if this area is larger.

Return `best`.

## Correctness

The algorithm considers every possible choice of three different points because the three nested loops enumerate all index triples `i < j < k`.

For each such triple, the cross product formula computes the exact area of the triangle formed by those three points. The absolute value handles orientation, so the result is always non-negative.

The variable `best` is updated with the maximum area seen so far. After all triples have been processed, every valid triangle has been considered, and `best` is the largest area among them.

Therefore, the algorithm returns the required largest triangle area.

## Complexity

Let `n = len(points)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^3)` | We check every triplet of points |
| Space | `O(1)` | Only a few numeric variables are stored |

With `n <= 50`, this is easily fast enough.

## Implementation

```python
class Solution:
    def largestTriangleArea(self, points: list[list[int]]) -> float:
        def area(a: list[int], b: list[int], c: list[int]) -> float:
            x1, y1 = a
            x2, y2 = b
            x3, y3 = c

            return abs(
                (x2 - x1) * (y3 - y1)
                - (x3 - x1) * (y2 - y1)
            ) / 2

        n = len(points)
        best = 0.0

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    best = max(best, area(points[i], points[j], points[k]))

        return best
```

## Code Explanation

The helper function extracts the coordinates:

```python
x1, y1 = a
x2, y2 = b
x3, y3 = c
```

Then it computes the area using the determinant form of the cross product:

```python
abs(
    (x2 - x1) * (y3 - y1)
    - (x3 - x1) * (y2 - y1)
) / 2
```

The absolute value is needed because the sign depends on the order of the points.

The loops choose every distinct triplet once:

```python
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
```

Each area is compared with the current best answer:

```python
best = max(best, area(points[i], points[j], points[k]))
```

Finally, `best` is returned.

## Testing

```python
def close(a, b, eps=1e-5):
    return abs(a - b) <= eps

def run_tests():
    s = Solution()

    assert close(
        s.largestTriangleArea([[0, 0], [0, 1], [1, 0], [0, 2], [2, 0]]),
        2.0,
    )

    assert close(
        s.largestTriangleArea([[1, 0], [0, 0], [0, 1]]),
        0.5,
    )

    assert close(
        s.largestTriangleArea([[0, 0], [1, 1], [2, 2]]),
        0.0,
    )

    assert close(
        s.largestTriangleArea([[-1, 0], [1, 0], [0, 2], [0, -2]]),
        4.0,
    )

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Official sample with five points | Checks choosing the best among many triplets |
| Three points only | Minimum valid input |
| Collinear points | Area should be zero |
| Negative coordinates | Confirms the formula works across quadrants |