963. Minimum Area Rectangle II

963. Minimum Area Rectangle II (Medium)

Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.

If there isn't any rectangle, return 0.

 

Example 1:

Input: [[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: [[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: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

Example 4:

Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.

 

Note:

1. 1 <= points.length <= 50
2. 0 <= points[i][0] <= 40000
3. 0 <= points[i][1] <= 40000
4. All points are distinct.
5. Answers within 10^-5 of the actual value will be accepted as correct.

Related Topics:
Math, Geometry

Solution 1.

Intuition

For each triangle, let's try to find the 4th point and whether it is a rectangle.

Algorithm

Say the first 3 points are p1, p2, p3, and that p2 and p3 are opposite corners of the final rectangle. The 4th point must be p4 = p2 + p3 - p1 (using vector notation) because p1, p2, p4, p3 must form a parallelogram, and p1 + (p2 - p1) + (p3 - p1) = p4.

If this point exists in our collection (we can use a set to check), then we should check that the angles of this parallelogram are 90 degrees. The easiest way is to check the dot product of the two vectors (p2 - p1) and (p3 - p1). (Another way is that we could normalize the vectors to length 1, and check that one equals the other rotated by 90 degrees.)

// OJ: https://leetcode.com/problems/minimum-area-rectangle-ii/
// Author: github.com/lzl124631x
// Time: O(N^3)
// Space: O(N)
// Ref: https://leetcode.com/problems/minimum-area-rectangle-ii/solution/
class Solution {
    double dist(vector<int> &a, vector<int> &b) {
        return sqrt(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2));
    }
public:
    double minAreaFreeRect(vector<vector<int>>& A) {
        int N = A.size();
        set<vector<int>> s(begin(A), end(A));
        double ans = DBL_MAX;
        for (int i = 0; i < N; ++i) {
            auto &p1 = A[i];
            for (int j = 0; j < N; ++j) {
                if (i == j) continue;
                auto &p2 = A[j];
                for (int k = j + 1; k < N; ++k) {
                    if (k == i) continue;
                    auto &p3 = A[k], p4 = vector<int>{ p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1] };
                    if (s.count(p4)) {
                        int dot = (p2[0] - p1[0]) * (p3[0] - p1[0]) + (p2[1] - p1[1]) * (p3[1] - p1[1]);
                        if (dot == 0) {
                            double area = dist(p1, p2) * dist(p1, p3);
                            ans = min(ans, area);
                        }
                    }
                }
            }
        }
        return ans == DBL_MAX ? 0 : ans;
    }
};

Solution 2. Map

1. Two diagonals of a rectangle bisect each other, and are of equal length.
2. A map's key is a string including diagonal length and coordinate of the diagonal center; A map's value is a vector of index pairs of two points forming the diagonal.

The first part takes O(N^2) time.

For the second part, according to the Theorem 9 in Finding squares and rectangles in sets of points. M.J. van Kreveld and M.T. de Berg, there are at most O(N^2 * sqrt(N)) rectangles with these N points, so the time complexity is O(N^2 * sqrt(N)).

// OJ: https://leetcode.com/problems/minimum-area-rectangle-ii/
// Author: github.com/lzl124631x
// Time: O(N^2 * sqrt(N))
// Space: O(N^2)
// Ref: https://leetcode.com/problems/minimum-area-rectangle-ii/discuss/208361/JAVA-O(n2)-using-Map
class Solution {
    inline long distance(vector<int> &a, vector<int> &b) {
        return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
    }
public:
    double minAreaFreeRect(vector<vector<int>>& A) {
        int N = A.size();
        double ans = DBL_MAX;
        if (N < 4) return 0;
        unordered_map<string, vector<vector<int>>> m;
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                long dist = distance(A[i], A[j]);
                double centerX = (A[i][0] + A[j][0]) / 2.0;
                double centerY = (A[i][1] + A[j][1]) / 2.0;
                auto key = to_string(dist) + "," + to_string(centerX) + "," + to_string(centerY);
                m[key].push_back({ i, j });
            }
        }
        for (auto &[key, val] : m) {
            if (val.size() <= 1) continue;
            for (int i = 0; i < val.size(); ++i) {
                for (int j = i + 1; j < val.size(); ++j) {
                    int a = val[i][0], b = val[i][1], c = val[j][0];
                    double len1 = sqrt(distance(A[a], A[c]));
                    double len2 = sqrt(distance(A[b], A[c]));
                    ans = min(ans, len1 * len2);
                }
            }
        }
        return ans == DBL_MAX ? 0 : ans;
    }
};