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