【多维分桶】最小面积矩形

摘要: 分桶算法的在计算几何的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在计算几何中，分桶是一种常用的算法，例如 N 个点中最多有多少点共线，本文我们继续看一个分桶处理的问题：最小面积矩形。首先看简单情形，矩形的边均平行于坐标轴，然后是较复杂的情形，矩形的边可以不平行于坐标轴。

---

939. 最小面积矩形

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

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

提示：

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

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

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

算法1: 按坐标排序

将点按照纵坐标排序。用 treemap 维护， key 为 y，值为纵坐标为 y 的点的横坐标的集合。

map<int, unordered_set<int>> mapping;

按顺序枚举纵坐标 y1，对横坐标集合 mapping[y1] 中的每一对横坐标 (x1, x2)，看是否同时在某个后续的 mapping[y2] 中出现，从小到大枚举 y2，只要找到 (x1, x2) 同时出现，就可以不再向后枚举 y2 了。

代码 (C++)

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        int n = points.size();
        map<int, unordered_set<int>> mapping;
        for(int i = 0; i < n; ++i)
        {
            int x = points[i][0], y = points[i][1];
            mapping[y].insert(x);
        }
        int ans = INT_MAX / 2;
        auto it = mapping.begin();
        while(it != mapping.end())
        {
            int y0 = it -> first;
            vector<int> xs((it -> second).begin(), (it -> second).end());
            ++it;
            int m = xs.size();
            if(m == 1)
                continue;
            for(int i = 0; i < m - 1; ++i)
                for(int j = i + 1; j < m; ++j)
                {
                    int x1 = xs[i];
                    int x2 = xs[j];
                    auto ity = it;
                    while(ity != mapping.end())
                    {
                        if((ity -> second).count(x1) > 0 && (ity -> second).count(x2) > 0)
                        {
                            ans = min(ans, abs(x1 - x2) * abs(ity -> first - y0));
                            break;
                        }
                        ++ity;
                    }
                }
        }
        if(ans == INT_MAX / 2)
            return 0;
        return ans;
    }
};

算法2: 枚举对角线

枚举对角线的两个点 (x1, y1), (x2, y2)，看另外两个点 (x1, y2), (x2, y1) 是否同时在点集中。

代码 (C++)

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        unordered_set<int> setting;
        int base = 4e4 + 7;
        for(vector<int>& p: points)
            setting.insert(p[0] * base + p[1]);
        int n = points.size();
        int ans = INT_MAX / 2;
        for(int i = 0; i < n - 1; ++i)
            for(int j = i + 1; j < n; ++j)
            {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if(x1 == x2 || y1 == y2)
                    continue;
                if(setting.count(x1 * base + y2) > 0 && setting.count(x2 * base + y1) > 0)
                    ans = min(ans, abs(x1 - x2) * abs(y1 - y2));
            }
        if(ans == INT_MAX / 2)
            return 0;
        return ans;
    }
};

---

963. 最小面积矩形 II

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

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

提示：

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

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

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

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

示例 4：
输入：[[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: 枚举对角线和第三点

枚举对角线p1, p2，和第三点 p3, 第四点可以用向量运算求出 p4 = p1 + p2 - p3

此时判定 p4 是否在点集中。如果再，再判断 (p1 - p3) 与 (p2 - p3) 的内积是否为 0。

代码 (C++)

其中向量操作使用模板 【模板】向量的实现。

class Solution {
public:
    double minAreaFreeRect(vector<vector<int>>& points) {
        using ll = long long;
        int n = points.size();
        ll base = 4e4 + 5;
        unordered_set<ll> setting;
        for(int i = 0; i < n; ++i)
            setting.insert(points[i][0] * base + points[i][1]);
        double ans = INT_MAX;
        for(int i = 0; i < n - 1; ++i)
            for(int j = i + 1; j < n; ++j)
            {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                Vector2 p1(x1, y1), p2(x2, y2);
                // p1, p2 是对角线
                for(int k = 0; k < n; ++k)
                {
                    if(k == i || k == j)
                        continue;
                    int x3 = points[k][0], y3 = points[k][1];
                    Vector2 p3(x3, y3);
                    int x4 = x1 + x2 - x3, y4 = y1 + y2 - y3;
                    if(setting.count(x4 * base + y4) > 0)
                        if(fabs((p1 - p3).dot(p2 - p3)) < EPS)
                            ans = min(ans, (p1 - p3).norm() * (p2 - p3).norm());
                }
            }
        if(fabs(ans - INT_MAX) < EPS)
            return 0;
        return ans;
    }
};

算法2: 枚举点对，按(中点,长度)分桶

枚举点对 pi, pj，求其中点 ((pi.x + pj.x)/2, (pi.y + pj.y)/2), 以及长度 (pi - pj).norm()。

将中点坐标和点对的长度打包成一个结构体 Info，定义求哈希值的方法和相等判定方法。然后用以 Info 为键的 HashMap 维护 pi。

struct Info
{
    Vector2 mid;
    LD len;
    Info(Vector2 p, LD len):mid(p),len(len){}
};

struct MyCmp
{
    bool operator()(const Info& info1, const Info& info2) const
    {
        return (info1.mid == info2.mid && fabs(info1.len - info2.len) < EPS);
    }
};

struct MyHash
{
    LD operator()(const Info& info) const
    {
        return info.len * base * base + info.mid.x * base + info.mid.y;
    }
};

mapping[info] 中，一对点只用存一个 pi，因为 pj 可以根据 pi 和中点通过向量操作求出来。

代码 (C++)

using LD = long double;
LD base = 4e4 + 7;

struct Info
{
    Vector2 mid;
    LD len;
    Info(Vector2 p, LD len):mid(p),len(len){}
};

struct MyCmp
{
    bool operator()(const Info& info1, const Info& info2) const
    {
        return (info1.mid == info2.mid && fabs(info1.len - info2.len) < EPS);
    }
};

struct MyHash
{
    // long double 型哈希值
    LD operator()(const Info& info) const
    {
        return info.len * base * base + info.mid.x * base + info.mid.y;
    }
};

class Solution {
public:
    double minAreaFreeRect(vector<vector<int>>& points) {
        int n = points.size();
        vector<Vector2> ps(n);
        for(int i = 0; i < n; ++i)
        {
            ps[i].x = points[i][0];
            ps[i].y = points[i][1];
        }
        unordered_map<Info, vector<Vector2>, MyHash, MyCmp> mapping;
        for(int i = 0; i < n - 1; ++i)
            for(int j = i + 1; j < n; ++j)
            {
                Vector2 p1 = ps[i], p2 = ps[j];
                Vector2 mid = (p1 + p2) * 0.5;
                LD len = (p1 - p2).norm();
                Info info(mid, len);
                mapping[info].push_back(p1);
            }
        double ans = INT_MAX;
        auto it = mapping.begin();
        while(it != mapping.end())
        {
            if((it -> second).size() == 1)
            {
                ++it;
                continue;
            }
            int m = (it -> second).size();
            for(int i = 0; i < m - 1; ++i)
            {
                Vector2 p1 = (it -> second)[i];
                for(int j = i + 1; j < m; ++j)
                {
                    Vector2 p2 = (it -> second)[j];
                    if(fabs((p2 - (it -> first).mid).cross(p1 - (it -> first).mid)) < EPS)
                        continue;
                    double delta_x = (it -> first).mid.x - p1.x;
                    double delta_y = (it -> first).mid.y - p1.y;
                    Vector2 p3(p1.x + delta_x * 2, p1.y + delta_y * 2);
                    ans = min(ans, (p2 - p1).norm() * (p2 - p3).norm());
                }
            }
            ++it;
        }
        if(fabs(ans - INT_MAX) < EPS)
            return 0;
        return ans;
    }
};

算法3: 用多层 TreeMap 对多属性分桶

代码 (C++)

class Solution {
public:
    double minAreaFreeRect(vector<vector<int>>& points) {
        int n = points.size();
        vector<Vector2> ps(n);
        for(int i = 0; i < n; ++i)
        {
            ps[i].x = points[i][0];
            ps[i].y = points[i][1];
        }
        map<double, map<Vector2, vector<Vector2>>> mapping;
        for(int i = 0; i < n - 1; ++i)
            for(int j = i + 1; j < n; ++j)
            {
                Vector2 p1 = ps[i], p2 = ps[j];
                Vector2 mid = (p1 + p2) * 0.5;
                double len = (p1 - p2).norm();
                mapping[len][mid].push_back(p1);
            }
        double ans = INT_MAX;
        auto it_len = mapping.begin();
        while(it_len != mapping.end())
        {
            double len = it_len -> first;
            const auto &sub_mapping = mapping[len];
            ++it_len;
            auto it_mid = sub_mapping.begin();
            while(it_mid != sub_mapping.end())
            {
                const Vector2 &mid = it_mid -> first;
                const vector<Vector2> &cand = it_mid -> second;
                ++it_mid;
                int m = cand.size();
                if(m == 1)
                    continue;
                for(int i = 0; i < m - 1; ++i)
                {
                    Vector2 p1 = cand[i];
                    for(int j = i + 1; j < m; ++j)
                    {
                        Vector2 p2 = cand[j];
                        if(fabs((p2 - mid).cross(p1 - mid)) < EPS)
                            continue;
                        double delta_x = mid.x - p1.x;
                        double delta_y = mid.y - p1.y;
                        Vector2 p3(p1.x + delta_x * 2, p1.y + delta_y * 2);
                        ans = min(ans, (p2 - p1).norm() * (p2 - p3).norm());
                    }
                }
            }
        }
        if(fabs(ans - INT_MAX) < EPS)
            return 0;
        return ans;
    }
};

---