Skip to content

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<vector<int>>& points) {
    long ans = LONG_MAX;
    // For each A, B pair points, {hash(A, B): (ax, ay, bx, by)}.
    unordered_map<int, vector<tuple<int, int, int, int>>> centerToPoints;

    for (const vector<int>& A : points)
      for (const vector<int>& 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<int>& p, const vector<int>& 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<Integer, List<int[]>> 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<int[]> 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 math.sqrt(ans)