# LeetCode 963: Minimum Area Rectangle II

## Problem Restatement

We are given a list of unique points in the `x-y` plane.

Each point is:

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

We need to find the minimum area of any rectangle formed by four of these points.

The rectangle sides do not need to be parallel to the axes. A rotated rectangle is allowed.

If no rectangle can be formed, return `0`.

Answers within `10^-5` of the actual answer are accepted. The official constraints allow up to `50` unique points, with coordinates from `0` to `4 * 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `points`, a list of unique 2D points |
| Output | Minimum rectangle area as a float |
| Rectangle rule | Sides may be rotated, not necessarily axis-aligned |
| No rectangle | Return `0` |

Example function shape:

```python
def minAreaFreeRect(points: list[list[int]]) -> float:
    ...
```

## Examples

Example 1:

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

Output:

```python
2.00000
```

These four points form a rotated square with area `2`.

Example 2:

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

Output:

```python
1.00000
```

The rectangle can be formed by:

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

Its area is `1`.

Example 3:

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

Output:

```python
0
```

No rectangle can be formed.

## First Thought: Pick Four Points

A direct approach is to try every group of four points and check whether they form a rectangle.

There are:

```python
O(n^4)
```

groups.

Since `n <= 50`, this may still be large and awkward to implement correctly.

We need a cleaner geometry test.

## Key Insight

A rectangle has a useful diagonal property.

For any rectangle:

1. The two diagonals have the same midpoint.
2. The two diagonals have the same length.

So instead of choosing four points directly, we can choose pairs of points as possible diagonals.

If two point pairs share the same midpoint and the same squared distance, then they are the diagonals of a rectangle.

Example:

```python
A ----- B
|       |
D ----- C
```

The diagonals are:

```python
A-C
B-D
```

They have the same midpoint and the same length.

This works for rotated rectangles too.

## Avoiding Floating-Point Midpoints

Instead of storing the midpoint as:

```python
((x1 + x2) / 2, (y1 + y2) / 2)
```

we store doubled midpoint coordinates:

```python
x1 + x2
y1 + y2
```

This avoids floating-point precision issues.

We also store squared diagonal length:

```python
(x1 - x2)^2 + (y1 - y2)^2
```

So each pair of points belongs to a group key:

```python
(mid_x_sum, mid_y_sum, diagonal_length_squared)
```

Pairs in the same group are possible diagonal pairs of rectangles.

## Computing Area

Suppose two diagonals are:

```python
A-C
B-D
```

If they are in the same group, they form a rectangle.

To compute the area, choose one endpoint from the first diagonal, say `A`.

The two adjacent vertices are `B` and `D`.

The side lengths are:

```python
distance(A, B)
distance(A, D)
```

So the rectangle area is:

```python
distance(A, B) * distance(A, D)
```

where these are ordinary Euclidean distances.

To reduce square roots, compute squared side lengths first:

```python
area = sqrt(side1_squared * side2_squared)
```

## Algorithm

1. Create a dictionary:

```python
groups[key] = list of point pairs
```

2. For every pair of points `(p1, p2)`:
   - Compute doubled midpoint.
   - Compute squared distance.
   - Store the pair in its group.
3. For each group:
   - Try every two pairs in the group.
   - They represent two diagonals of a rectangle.
   - Compute the rectangle area.
   - Keep the minimum area.
4. If no rectangle was found, return `0`.
5. Otherwise, return the minimum area.

## Correctness

Every rectangle has two diagonals with the same midpoint and the same length. Therefore, when the algorithm groups all point pairs by doubled midpoint and squared distance, the two diagonals of any valid rectangle must appear in the same group.

Now consider two different point pairs in the same group. They have the same midpoint and the same diagonal length. A quadrilateral whose diagonals bisect each other is a parallelogram. A parallelogram whose diagonals have equal length is a rectangle. Therefore, these two pairs form a rectangle.

For each such pair of diagonals, the algorithm computes the area using two adjacent sides from one endpoint. This gives the exact rectangle area.

Since the algorithm considers every pair of points as a possible diagonal, it considers every possible rectangle. Since it keeps the minimum area among all found rectangles, the returned value is the minimum possible rectangle area.

If no two diagonal pairs share a valid group, then no rectangle exists, and returning `0` is correct.

## Complexity

Let `n = len(points)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2 + k)` | We group all point pairs, then compare pairs inside each group |
| Worst-case time | `O(n^4)` | A large group may contain many pairs |
| Space | `O(n^2)` | We store all point pairs |

With `n <= 50`, this is acceptable.

## Implementation

```python
from collections import defaultdict
from math import sqrt

class Solution:
    def minAreaFreeRect(self, points: list[list[int]]) -> float:
        n = len(points)
        groups = defaultdict(list)

        for i in range(n):
            x1, y1 = points[i]

            for j in range(i + 1, n):
                x2, y2 = points[j]

                mid_x = x1 + x2
                mid_y = y1 + y2
                dist2 = (x1 - x2) ** 2 + (y1 - y2) ** 2

                key = (mid_x, mid_y, dist2)
                groups[key].append((x1, y1, x2, y2))

        best = float("inf")

        for pairs in groups.values():
            m = len(pairs)

            for i in range(m):
                ax, ay, cx, cy = pairs[i]

                for j in range(i + 1, m):
                    bx, by, dx, dy = pairs[j]

                    side1 = (ax - bx) ** 2 + (ay - by) ** 2
                    side2 = (ax - dx) ** 2 + (ay - dy) ** 2

                    area = sqrt(side1 * side2)
                    best = min(best, area)

        if best == float("inf"):
            return 0

        return best
```

## Code Explanation

We group all point pairs as possible diagonals:

```python
groups = defaultdict(list)
```

For each pair:

```python
mid_x = x1 + x2
mid_y = y1 + y2
dist2 = (x1 - x2) ** 2 + (y1 - y2) ** 2
```

The key means:

```python
same center and same diagonal length
```

Then:

```python
groups[key].append((x1, y1, x2, y2))
```

stores that pair as a possible diagonal.

For every group, we compare two diagonals:

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

Take one endpoint from the first diagonal:

```python
ax, ay
```

and both endpoints from the second diagonal:

```python
(bx, by), (dx, dy)
```

These are adjacent vertices to `A`.

Compute squared side lengths:

```python
side1 = (ax - bx) ** 2 + (ay - by) ** 2
side2 = (ax - dx) ** 2 + (ay - dy) ** 2
```

Then compute the area:

```python
area = sqrt(side1 * side2)
```

Finally, return the best area found:

```python
return 0 if best == float("inf") else best
```

## Testing

```python
def run_tests():
    s = Solution()

    assert abs(
        s.minAreaFreeRect([[1, 2], [2, 1], [1, 0], [0, 1]]) - 2.0
    ) < 1e-5

    assert abs(
        s.minAreaFreeRect([[0, 1], [2, 1], [1, 1], [1, 0], [2, 0]]) - 1.0
    ) < 1e-5

    assert s.minAreaFreeRect([[0, 3], [1, 2], [3, 1], [1, 3], [2, 1]]) == 0

    assert abs(
        s.minAreaFreeRect([[3, 1], [1, 1], [0, 1], [2, 1], [3, 3], [3, 2], [0, 2], [2, 3]]) - 2.0
    ) < 1e-5

    assert s.minAreaFreeRect([[0, 0], [1, 1], [2, 2]]) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Rotated square | Checks non-axis-aligned rectangle |
| Axis-aligned rectangle | Valid rectangle is still allowed |
| No rectangle | Returns `0` |
| Larger mixed set | Finds minimum among several candidates |
| Three collinear points | Cannot form a rectangle |