Leetcode 1003 Solution

This article provides solution to leetcode question 1003 (minimum-area-rectangle-ii)

https://leetcode.com/problems/minimum-area-rectangle-ii

Solution

class Solution:
    def minAreaFreeRect(self, points: List[List[int]]) -> float:
        points = [complex(*z) for z in points]

        m = collections.defaultdict(list)

        for pt1, pt2 in itertools.combinations(points, 2):
            center = (pt1 + pt2) / 2
            radius = abs(center - pt1)
            m[(center, radius)].append(pt1)

        ans = float("inf")
        for (center, radius), pts in m.items():
            for pt1, pt2 in itertools.combinations(pts, 2):
                ans = min(ans, abs(pt1 - pt2) * abs(pt1 - (2*center - pt2)))

        return ans if ans < float("inf") else 0