题目描述

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

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

样例

输入：[[1,2],[2,1],[1,0],[0,1]]
输出：2.00000
解释：最小面积的矩形出现在 [1,2],[2,1],[1,0],[0,1] 处，面积为 2。

输入：[[0,1],[2,1],[1,1],[1,0],[2,0]]
输出：1.00000
解释：最小面积的矩形出现在 [1,0],[1,1],[2,1],[2,0] 处，面积为 1。

输入：[[0,3],[1,2],[3,1],[1,3],[2,1]]
输出：0
解释：没法从这些点中组成任何矩形。

输入：[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
输出：2.00000
解释：最小面积的矩形出现在 [2,1],[2,3],[3,3],[3,1] 处，面积为 2。

注意

• 1 <= points.length <= 50
• 0 <= points[i][0] <= 40000
• 0 <= points[i][1] <= 40000
• 所有的点都是不同的。
• 与真实值误差不超过 10^-5 的答案将视为正确结果。

算法

(枚举) $O(n^3)$

1. 将所有点加入哈希表中。
2. 每次枚举三个点 x, y, z，以这三个点尝试构成矩形的一组邻边，共有三种情况。假设 (x, y) 和 (x, z) 构成一组邻边，判定其是否垂直，即点乘为 0。然后，通过向量运算求出另一个点 p，使得 (x, y) 与 (z, p) 是相同的向量。在哈希表中判断 p 是否存在即可。

时间复杂度

• 每次枚举三个点，判定的时间复杂度为常数，故总时间复杂度为 $O(n^3)$。

C++ 代码

class Solution {
public:
    void update(const vector<int> &x, const vector<int> &y,
                const vector<int> &z, double &ans,
                const unordered_set<string>& h) {

        vector<int> l0(2), l1(2);
        vector<int> p(2);

        l0[0] = x[0] - y[0];
        l0[1] = x[1] - y[1];
        l1[0] = x[0] - z[0];
        l1[1] = x[1] - z[1];

        if (l0[0] * l1[0] + l0[1] * l1[1] == 0) { 
            p[0] = z[0] - l0[0];
            p[1] = z[1] - l0[1];

            if (h.find(to_string(p[0]) + " " + to_string(p[1])) != h.end()) {
                ans = min(ans, sqrt(l0[0] * l0[0] + l0[1] * l0[1])
                             * sqrt(l1[0] * l1[0] + l1[1] * l1[1])
                         );
            }
        }

    }

    double minAreaFreeRect(vector<vector<int>>& points) {
        int n = points.size();

        unordered_set<string> h;

        for (int i = 0; i < n; i++)
            h.insert(to_string(points[i][0]) + " " + to_string(points[i][1]));

        double ans = 1e100;

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++) {
                    update(points[i], points[j], points[k], ans, h);
                    update(points[j], points[i], points[k], ans, h);
                    update(points[k], points[i], points[j], ans, h);
                }
        if (ans == 1e100)
            ans = 0;
        return ans;
    }
};