Skip to content

963. Minimum Area Rectangle II

DifficultyMedium

Description

You are given an array of points in the X-Y plane points where points[i] = [xi, yi].

Return the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the X and Y axes. If there is not any such rectangle, return 0.

Answers within 10-5 of the actual answer will be accepted.

 

Example 1:

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.

Example 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.

Example 3:

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.

 

Constraints:

  • 1 <= points.length <= 50
  • points[i].length == 2
  • 0 <= xi, yi <= 4 * 104
  • All the given points are unique.

Solutions

Solution 1: Hash Table + Enumeration

Thinking

The smallest area of a (possibly rotated) rectangle, \(n\le 50\), allows enumerating three vertices. With a right angle at \(p_1\), the fourth corner is the vector sum of the two edges.

The packed key \(x \times 40001 + y\) repeats once a coordinate leaves \([0, 4 \times 10^4]\), and the sum of two squared edges exceeds \(2^{31}-1\).

Inside that square the key is unique, and those squares fit in a 64-bit integer.

The fourth corner is accepted only when both coordinates lie in range and the key is present. Squared edge lengths are accumulated in 64 bits before the square root.

We use a hash table to store all the points, then enumerate three points \(p_1 = (x_1, y_1)\), \(p_2 = (x_2, y_2)\), \(p_3 = (x_3, y_3)\). If \(\overrightarrow{p_1p_2}\) and \(\overrightarrow{p_1p_3}\) are perpendicular, the fourth corner is \((x_4, y_4)=(x_2 - x_1 + x_3, y_2 - y_1 + y_3)\). Coordinates lie in \([0, 4 \times 10^4]\), and the packed key \(x \times 40001 + y\) is unique only inside that square, so this corner counts only when both coordinates fall in range and the key is present. The squared edge lengths are summed in 64-bit integers, since each sum can exceed \(2^{31}-1\), and the area is the square root of their product.

Finally, if a rectangle that satisfies the conditions is found, return the minimum area among them. Otherwise, return \(0\).

The time complexity is \(O(n^3)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{points}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def minAreaFreeRect(self, points: List[List[int]]) -> float:
        s = {(x, y) for x, y in points}
        n = len(points)
        ans = inf
        for i in range(n):
            x1, y1 = points[i]
            for j in range(n):
                if j != i:
                    x2, y2 = points[j]
                    for k in range(j + 1, n):
                        if k != i:
                            x3, y3 = points[k]
                            x4 = x2 - x1 + x3
                            y4 = y2 - y1 + y3
                            if 0 <= x4 <= 40000 and 0 <= y4 <= 40000 and (x4, y4) in s:
                                v21 = (x2 - x1, y2 - y1)
                                v31 = (x3 - x1, y3 - y1)
                                if v21[0] * v31[0] + v21[1] * v31[1] == 0:
                                    w = sqrt(v21[0] ** 2 + v21[1] ** 2)
                                    h = sqrt(v31[0] ** 2 + v31[1] ** 2)
                                    ans = min(ans, w * h)
        return 0 if ans == inf else ans

 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
class Solution {
    public double minAreaFreeRect(int[][] points) {
        int n = points.length;
        Set<Integer> s = new HashSet<>(n);
        for (int[] p : points) {
            s.add(f(p[0], p[1]));
        }
        double ans = Double.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            int x1 = points[i][0], y1 = points[i][1];
            for (int j = 0; j < n; ++j) {
                if (j != i) {
                    int x2 = points[j][0], y2 = points[j][1];
                    for (int k = j + 1; k < n; ++k) {
                        if (k != i) {
                            int x3 = points[k][0], y3 = points[k][1];
                            int x4 = x2 - x1 + x3, y4 = y2 - y1 + y3;
                            if (x4 >= 0 && x4 <= 40000 && y4 >= 0 && y4 <= 40000
                                && s.contains(f(x4, y4))) {
                                if ((x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1) == 0) {
                                    long ww = (long) (x2 - x1) * (x2 - x1)
                                        + (long) (y2 - y1) * (y2 - y1);
                                    long hh = (long) (x3 - x1) * (x3 - x1)
                                        + (long) (y3 - y1) * (y3 - y1);
                                    ans = Math.min(ans, Math.sqrt(ww * hh));
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans == Double.MAX_VALUE ? 0 : ans;
    }

    private int f(int x, int y) {
        return x * 40001 + y;
    }
}

 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
class Solution {
public:
    double minAreaFreeRect(vector<vector<int>>& points) {
        auto f = [](int x, int y) {
            return x * 40001 + y;
        };
        int n = points.size();
        unordered_set<int> s;
        for (auto& p : points) {
            s.insert(f(p[0], p[1]));
        }
        double ans = 1e20;
        for (int i = 0; i < n; ++i) {
            int x1 = points[i][0], y1 = points[i][1];
            for (int j = 0; j < n; ++j) {
                if (j != i) {
                    int x2 = points[j][0], y2 = points[j][1];
                    for (int k = j + 1; k < n; ++k) {
                        if (k != i) {
                            int x3 = points[k][0], y3 = points[k][1];
                            int x4 = x2 - x1 + x3, y4 = y2 - y1 + y3;
                            if (x4 >= 0 && x4 <= 40000 && y4 >= 0 && y4 <= 40000 && s.count(f(x4, y4))) {
                                if ((x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1) == 0) {
                                    long long ww = (long long) (x2 - x1) * (x2 - x1) + (long long) (y2 - y1) * (y2 - y1);
                                    long long hh = (long long) (x3 - x1) * (x3 - x1) + (long long) (y3 - y1) * (y3 - y1);
                                    ans = min(ans, sqrt(ww * hh));
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans == 1e20 ? 0 : ans;
    }
};

 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
func minAreaFreeRect(points [][]int) float64 {
    n := len(points)
    f := func(x, y int) int {
        return x*40001 + y
    }
    s := map[int]bool{}
    for _, p := range points {
        s[f(p[0], p[1])] = true
    }
    ans := 1e20
    for i := 0; i < n; i++ {
        x1, y1 := points[i][0], points[i][1]
        for j := 0; j < n; j++ {
            if j != i {
                x2, y2 := points[j][0], points[j][1]
                for k := j + 1; k < n; k++ {
                    if k != i {
                        x3, y3 := points[k][0], points[k][1]
                        x4, y4 := x2-x1+x3, y2-y1+y3
                        if x4 >= 0 && x4 <= 40000 && y4 >= 0 && y4 <= 40000 && s[f(x4, y4)] {
                            if (x2-x1)*(x3-x1)+(y2-y1)*(y3-y1) == 0 {
                                ww := (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)
                                hh := (x3-x1)*(x3-x1) + (y3-y1)*(y3-y1)
                                ans = math.Min(ans, math.Sqrt(float64(ww*hh)))
                            }
                        }
                    }
                }
            }
        }
    }
    if ans == 1e20 {
        return 0
    }
    return ans
}

 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
function minAreaFreeRect(points: number[][]): number {
    const n = points.length;
    const f = (x: number, y: number): number => x * 40001 + y;
    const s: Set<number> = new Set();
    for (const [x, y] of points) {
        s.add(f(x, y));
    }
    let ans = Number.MAX_VALUE;
    for (let i = 0; i < n; ++i) {
        const [x1, y1] = points[i];
        for (let j = 0; j < n; ++j) {
            if (j !== i) {
                const [x2, y2] = points[j];
                for (let k = j + 1; k < n; ++k) {
                    if (k !== i) {
                        const [x3, y3] = points[k];
                        const x4 = x2 - x1 + x3;
                        const y4 = y2 - y1 + y3;
                        if (x4 >= 0 && x4 <= 40000 && y4 >= 0 && y4 <= 40000 && s.has(f(x4, y4))) {
                            if ((x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1) === 0) {
                                const ww = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
                                const hh = (x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1);
                                ans = Math.min(ans, Math.sqrt(ww * hh));
                            }
                        }
                    }
                }
            }
        }
    }
    return ans === Number.MAX_VALUE ? 0 : ans;
}

Comments