Largest-Area Rectangle From a Point Set When Sides Need Not Be Axis-Aligned
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a set of distinct points with integer coordinates in the plane. Choose four of the points that are the corners of a rectangle, and return the largest area such a rectangle can have. The sides of the rectangle do not have to be parallel to the x- and y-axes. Return `0` if no four points form a rectangle.
### Function Signature
```python
def max_rectangle_area(points: list[list[int]]) -> int:
```
### Rules
- `points[i] = [x_i, y_i]`. The four chosen points must be distinct input points and must be exactly the four corners of the rectangle. Other input points may lie anywhere, including inside the rectangle or on its sides.
- A square counts as a rectangle.
- Because all coordinates are integers, the area of any such rectangle is an integer, so return it as an `int`.
### Constraints
- `1 <= len(points) <= 200`
- `0 <= x_i, y_i <= 40000`
- All points are distinct.
- The answer is at most `40000 * 40000 = 1,600,000,000`, which fits in a 32-bit signed integer, but intermediate values such as squared distances can reach `3,200,000,000`, which does not.
### Examples
**Example 1**
```text
Input: points = [[1, 2], [2, 1], [1, 0], [0, 1]]
Output: 2
```
The four points form a square rotated by 45 degrees, with side length $\sqrt{2}$.
**Example 2**
```text
Input: points = [[0, 1], [1, 0], [3, 2], [2, 3], [1, 1], [2, 1], [1, 2], [2, 2]]
Output: 4
```
`(0, 1)`, `(1, 0)`, `(3, 2)` and `(2, 3)` form a rectangle with side lengths $\sqrt{2}$ and $\sqrt{8}$, so its area is 4. The other rectangles in this set, such as the unit square `(1, 1)`, `(2, 1)`, `(2, 2)`, `(1, 2)`, are smaller.
**Example 3**
```text
Input: points = [[0, 0], [1, 0], [2, 1], [0, 1]]
Output: 0
```
The only four points do not form a rectangle.
Overview: Given distinct integer points in the plane, return the largest area of a rectangle whose four corners are input points, where the rectangle may be rotated rather than aligned with the axes. It tests the geometric characterization of rectangles, grouping point pairs efficiently, and exact integer arithmetic.
Read the full Google Software Engineer interview experience this question came from
You are given a set of distinct points with integer coordinates in the plane, as a list `points` where `points[i] = [x_i, y_i]`. Choose four of the points that are the corners of a rectangle, and return the largest area such a rectangle can have. The sides of the rectangle do not have to be parallel to the x- and y-axes. Return `0` if no four points form a rectangle.
### Rules
- The four chosen points must be distinct input points and must be exactly the four corners of the rectangle. Other input points may lie anywhere, including inside the rectangle or on its sides.
- A square counts as a rectangle.
- Because all coordinates are integers, the area of any such rectangle is an integer, so return it as an integer.
### Constraints
- `1 <= len(points) <= 200`
- `0 <= x_i, y_i <= 40000`
- All points are distinct.
- The answer is at most `40000 * 40000 = 1,600,000,000`, which fits in a signed 32-bit integer, so the return type is `int` in every language. Intermediate values such as squared distances can reach `3,200,000,000`, which exceeds `2^31 - 1`; compute them with 64-bit integers (`long` in Java, `long long` in C++).
### Example 1
```text
Input: points = [[1, 2], [2, 1], [1, 0], [0, 1]]
Output: 2
```
The four points form a square rotated by 45 degrees, with side length sqrt(2).
### Example 2
```text
Input: points = [[0, 1], [1, 0], [3, 2], [2, 3], [1, 1], [2, 1], [1, 2], [2, 2]]
Output: 4
```
`(0, 1)`, `(1, 0)`, `(3, 2)` and `(2, 3)` form a rectangle with side lengths sqrt(2) and sqrt(8), so its area is 4. The other rectangles in this set, such as the unit square `(1, 1)`, `(2, 1)`, `(2, 2)`, `(1, 2)`, are smaller.
Constraints
- 1 <= len(points) <= 200
- points[i] = [x_i, y_i] with 0 <= x_i, y_i <= 40000
- All points are distinct.
- The answer is at most 40000 * 40000 = 1,600,000,000, which fits in a signed 32-bit integer; intermediate values such as squared distances can reach 3,200,000,000, which exceeds 2^31 - 1 and needs 64-bit arithmetic (long in Java, long long in C++).
Examples
Input: ([[1, 2], [2, 1], [1, 0], [0, 1]],)
Expected Output: 2
Explanation: Source example 1: a square rotated by 45 degrees with side sqrt(2).
Input: ([[0, 1], [1, 0], [3, 2], [2, 3], [1, 1], [2, 1], [1, 2], [2, 2]],)
Expected Output: 4
Explanation: Source example 2: the tilted sqrt(2) x sqrt(8) rectangle beats the unit axis-aligned square; the inner points do not block it.
Hints
- The rectangle may be tilted: in Example 1 the four points form a square rotated by 45 degrees, so checking only axis-parallel sides is not enough.
- Other input points inside the rectangle or on its sides do not disqualify it; only the four corners have to be input points.
- Squared distances can reach 3,200,000,000, so keep length and area arithmetic in exact 64-bit integers instead of floating-point square roots.