Largest-Area Rectangle From a Point Set When Sides Need Not Be Axis-Aligned

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

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

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

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

Input: points = [[0, 0], [1, 0], [2, 1], [0, 1]]
Output: 0

The only four points do not form a rectangle.