LC 0963 [M] Minimum Area Rectangle II - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=FcWK8CJReUo&ab_channel=HappyCoding

class Solution:
    def minAreaFreeRect(self, points: List[List[int]]) -> float:
        def distance(p1, p2):
            d = (p1[0]-p2[0]) ** 2 + (p1[1]-p2[1]) ** 2
            return d
        
        # O(n^3): find points 1 by 1 then use pythas theorem and relationships to find 4th point
        '''
        ans = sys.maxsize
        points_set = set([(p[0],p[1]) for p in points])
        seen = set()
        
        for p1 in points_set:
            for p2 in points_set:
                if p1 == p2:
                    continue 
                    
                for p3 in seen:
                    if p1 == p3 or p2 == p3:
                        continue
                        
                    # find 3rd point
                    if distance(p1, p2) + distance(p2, p3) != distance(p1, p3): # pythagorean theorem
                        continue
                        
                    # find 4th point
                    x4 = p1[0] + p3[0] - p2[0]
                    y4 = p1[1] + p3[1] - p2[1]
                    # x1 + x3 = x2 + x4
                    # y1 + y3 + y2 + y4
                    if (x4, y4) in seen:
                        area = sqrt(distance(p1, p2)) * sqrt(distance(p2, p3))
                        # if area > 0:
                            # ans = min(ans, area)
                        ans = min(ans, area)
                        
            seen.add(p1)
                                     
        return ans if ans < sys.maxsize else 0
        '''                             
        
        # O(n^2): pre-build diagonals to fix the 2 points, with the same 2 lines across a center we know those 2 pairs can form a rectangle
        diagonals = defaultdict(list)
        n = len(points)
        
        for i in range(n): # most expensive part O(n^2)
            p1 = points[i]
            for j in range(i+1, n):
                p2 = points[j]
                center_x = (p1[0] + p2[0]) / 2
                center_y = (p1[1] + p2[1]) / 2
                length = distance(p1, p2)
                
                diagonals[(center_x, center_y, length)].append((p1, p2))
                
        ans = sys.maxsize
        
        for key in diagonals: # len of keys are much smaller
            points_pair_list = diagonals[key]
            n1 = len(points_pair_list)
            
            if n1 > 1: # 2 lines across this center
                for i in range(n1):
                    for j in range(i+1, n1):
                        p1 = points_pair_list[i][0]
                        p2 = points_pair_list[i][1]
                        p3 = points_pair_list[j][0]
                        p4 = points_pair_list[j][1]
                        
                        area = sqrt(distance(p1,p3)) * sqrt(distance(p1,p4))
                        ans = min(ans, area)
                        
        return ans if ans < sys.maxsize else 0