# 963. Minimum Area Rectangle II¶

• Time: $O(n^6)$
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public: double minAreaFreeRect(vector>& points) { long ans = LONG_MAX; // For each A, B pair points, {hash(A, B): (ax, ay, bx, by)}. unordered_map>> centerToPoints; for (const vector& A : points) for (const vector& B : points) { const int center = hash(A, B); centerToPoints[center].emplace_back(A[0], A[1], B[0], B[1]); } // For all pair points "that share the same center". for (const auto& [_, points] : centerToPoints) for (const auto& [ax, ay, bx, by] : points) for (const auto& [cx, cy, dx, dy] : points) // AC is perpendicular to AD. // AC dot AD = (cx - ax, cy - ay) dot (dx - ax, dy - ay) == 0. if ((cx - ax) * (dx - ax) + (cy - ay) * (dy - ay) == 0) { const long squaredArea = dist(ax, ay, cx, cy) * dist(ax, ay, dx, dy); if (squaredArea > 0) ans = min(ans, squaredArea); } return ans == LONG_MAX ? 0 : sqrt(ans); } private: int hash(const vector& p, const vector& q) { return ((long)(p[0] + q[0]) << 16) + (p[1] + q[1]); } long dist(int px, int py, int qx, int qy) { return (px - qx) * (px - qx) + (py - qy) * (py - qy); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public double minAreaFreeRect(int[][] points) { Long ans = Long.MAX_VALUE; // For each A, B pair points, {hash(A, B): (ax, ay, bx, by)}. Map> centerToPoints = new HashMap<>(); for (int[] A : points) for (int[] B : points) { int center = hash(A, B); if (centerToPoints.get(center) == null) centerToPoints.put(center, new ArrayList<>()); centerToPoints.get(center).add(new int[] {A[0], A[1], B[0], B[1]}); } // For all pair points "that share the same center". for (List pointPairs : centerToPoints.values()) for (int[] ab : pointPairs) for (int[] cd : pointPairs) { final int ax = ab[0], ay = ab[1]; final int cx = cd[0], cy = cd[1]; final int dx = cd[2], dy = cd[3]; // AC is perpendicular to AD. // AC dot AD = (cx - ax, cy - ay) dot (dx - ax, dy - ay) == 0. if ((cx - ax) * (dx - ax) + (cy - ay) * (dy - ay) == 0) { Long squaredArea = dist(ax, ay, cx, cy) * dist(ax, ay, dx, dy); if (squaredArea > 0) ans = Math.min(ans, squaredArea); } } return ans == Long.MAX_VALUE ? 0 : Math.sqrt(ans); } private int hash(int[] p, int[] q) { return ((p[0] + q[0]) << 16) + (p[1] + q[1]); } private Long dist(long px, long py, long qx, long qy) { return (px - qx) * (px - qx) + (py - qy) * (py - qy); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution: def minAreaFreeRect(self, points: List[List[int]]) -> float: ans = math.inf # For each A, B pair points, {hash(A, B): (ax, ay, bx, by)}. centerToPoints = collections.defaultdict(list) for ax, ay in points: for bx, by in points: center = ((ax + bx) / 2, (ay + by) / 2) centerToPoints[center].append((ax, ay, bx, by)) def dist(px: int, py: int, qx: int, qy: int) -> float: return (px - qx)**2 + (py - qy)**2 # For all pair points "that share the same center". for points in centerToPoints.values(): for ax, ay, _, _ in points: for cx, cy, dx, dy in points: # AC is perpendicular to AD. # AC dot AD = (cx - ax, cy - ay) dot (dx - ax, dy - ay) == 0. if (cx - ax) * (dx - ax) + (cy - ay) * (dy - ay) == 0: squaredArea = dist(ax, ay, cx, cy) * dist(ax, ay, dx, dy) if squaredArea > 0: ans = min(ans, squaredArea) return 0 if ans == math.inf else sqrt(ans)