[LeetCode] 963. Minimum Area Rectangle II

[grandyang]

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.

这道题是之前那道 Minimum Area Rectangle 的拓展，虽说是拓展，但是解题思想完全不同。那道题由于矩形不能随意翻转，所以任意两个相邻的顶点一定是相同的横坐标或者纵坐标，而这道题就不一样了，矩形可以任意翻转，就不能利用之前的特点了。那该怎么办呢，这里就要利用到矩形的对角线的特点了，我们都知道矩形的两条对角线长度是相等的，而且相交于矩形的中心，这个中心可以通过两个对顶点的坐标求出来。只要找到了两组对顶点，它们的中心重合，并且表示的对角线长度相等，则一定可以组成矩形。基于这种思想，可以遍历任意两个顶点，求出它们之间的距离，和中心点的坐标，将这两个信息组成一个字符串，建立和顶点在数组中位置之间的映射，这样能组成矩形的点就被归类到一起了。接下来就是遍历这个 HashMap 了，只能取出两组顶点及更多的地方，开始遍历，分别通过顶点的坐标算出两条边的长度，然后相乘用来更新结果 res 即可，参见代码如下：

class Solution {
public:
    double minAreaFreeRect(vector<vector<int>>& points) {
        int n = points.size();
        if (n < 4) return 0.0;
        double res = DBL_MAX;
        unordered_map<string, vector<vector<int>>> m;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                long dist = getLength(points[i], points[j]);
                double centerX = (points[i][0] + points[j][0]) / 2.0;
                double centerY = (points[i][1] + points[j][1]) / 2.0;
                string key = to_string(dist) + "_" + to_string(centerX) + "_" + to_string(centerY);
                m[key].push_back({i, j});
            }
        }
        for (auto &a : m) {
            vector<vector<int>> vec = a.second;
            if (vec.size() < 2) continue;
            for (int i = 0; i < vec.size(); ++i) {
                for (int j = i + 1; j < vec.size(); ++j) {
                    int p1 = vec[i][0], p2 = vec[j][0], p3 = vec[j][1];
                    double len1 = sqrt(getLength(points[p1], points[p2]));
                    double len2 = sqrt(getLength(points[p1], points[p3]));
                    res = min(res, len1 * len2);
                }
            }
        }
        return res == DBL_MAX ? 0.0 : res;
    }
    long getLength(vector<int>& pt1, vector<int>& pt2) {
        return (pt1[0] - pt2[0]) * (pt1[0] - pt2[0]) + (pt1[1] - pt2[1]) * (pt1[1] - pt2[1]);
    }
};

Github 同步地址:

#963

类似题目：

Minimum Area Rectangle

参考资料：

https://leetcode.com/problems/minimum-area-rectangle-ii/

https://leetcode.com/problems/minimum-area-rectangle-ii/discuss/208361/JAVA-O(n2)-using-Map

https://leetcode.com/problems/minimum-area-rectangle-ii/discuss/210786/C%2B%2B-with-picture-find-diagonals-O(n-*-n)

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

getLength 有可能会有overflow的问题吧，点是int 返回是long没用。比如 （0，0）and（40000， 40000）