Minimum Area Rectangle II Python Solution

lcpy gen -n 963   # by problem number
lcpy gen -s minimum_area_rectangle_ii   # by problem name

Input: points = [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Input: points = [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Input: points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

from collections import defaultdict
from itertools import combinations


class Solution:
    # Time: O(n^2 + sum(g^2)) over diagonal groups
    # Space: O(n^2)
    def min_area_free_rect(self, points: list[list[int]]) -> float:
        pts = [complex(x, y) for x, y in points]
        groups: dict[tuple[complex, float], list[tuple[complex, complex]]] = defaultdict(list)
        for p1, p2 in combinations(pts, 2):
            center = (p1 + p2) / 2
            diag_sq = abs(p1 - p2) ** 2
            groups[(center, diag_sq)].append((p1, p2))
        best = float("inf")
        for diags in groups.values():
            for (p1, p2), (p3, _p4) in combinations(diags, 2):
                area = abs(p1 - p3) * abs(p2 - p3)
                best = min(best, area)
        return best if best != float("inf") else 0.0