题目描述

给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。

如果没有任何矩形，就返回 0。

样例

输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4

输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2

注意

• 1 <= points.length <= 500
• 0 <= points[i][0] <= 40000
• 0 <= points[i][1] <= 40000
• 所有的点都是不同的。

算法

(枚举) $\Theta(n^2)$

1. 将所有点加入到哈希表中。
2. 枚举两个点，要求这两个点的横纵坐标均不相同。用哈希表判定，以这两个点为对顶点时的矩形的另外两个点是否存在。如果存在，则更新答案即可。

时间复杂度

• 哈希表的时间复杂度为常数，枚举的时间复杂度为 $\Theta(n^2)$，判定的时间复杂度为常数，故时间复杂度为 $\Theta(n^2)$。

C++ 代码

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        int n = points.size();
        unordered_set<unsigned> h;
        for (int i = 0; i < n; i++)
            h.insert(points[i][0] * 100000u + points[i][1]);

        int ans = INT_MAX;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (points[i][0] != points[j][0] && points[i][1] != points[j][1]) {
                    int x0 = points[i][0], x1 = points[j][0];
                    int y0 = points[i][1], y1 = points[j][1];
                    if (h.find(x0 * 100000u + y1) != h.end()
                     && h.find(x1 * 100000u + y0) != h.end())
                        ans = min(ans, (max(x0, x1) - min(x0, x1)) 
                                     * (max(y0, y1) - min(y0, y1))
                                 );
                }

        if (ans == INT_MAX)
            ans = 0;
        return ans;
    }
};