算法疑难杂症

力扣LCP37-最小矩形面积

字数统计: 2.7k字   |   阅读时长: 11分
, ,

摘要: LCP37，计算几何问题

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

今天我们来看一个比较难的计算几何题，力扣 LCP37，本题是2021力扣杯春季赛团队赛第5题。算法要点如下：

  • 两条直线的交点
  • 按斜率分桶
  • 细节处理

题目

二维平面上有 N 条直线，形式为 y = kx + b，其中 k、b 为整数 且 k > 0。所有直线以 [k,b] 的形式存于二维数组 lines 中，不存在重合的两条直线。两两直线之间可能存在一个交点，最多会有 $\binom{N}{2}$ 个交点。我们用一个平行于坐标轴的矩形覆盖所有的交点，请问这个矩形最小面积是多少。若直线之间无交点、仅有一个交点或所有交点均在同一条平行坐标轴的直线上，则返回0。

注意：返回结果是浮点数，与标准答案 绝对误差或相对误差 在 1e-4 以内的结果都被视为正确结果

限制：

1
2
3
4
1 <= lines.length <= 10^5 且 lines[i].length == 2
1 <= lines[0] <= 10000
-10000 <= lines[1] <= 10000
与标准答案绝对误差或相对误差在 10^-4 以内的结果都被视为正确结果

示例 1：
输入：lines = [[2,3],[3,0],[4,1]]
输出：48.00000
解释：三条直线的三个交点为 (3, 9) (1, 5) 和 (-1, -3)。最小覆盖矩形左下角为 (-1, -3) 右上角为 (3,9)，面积为 48

示例 2：
输入：lines = [[1,1],[2,3]]
输出：0.00000
解释：仅有一个交点 (-2，-1）

题解

算法：计算几何

给 n 条直线，求这 n 条直线的所有交点，然后统计答案也就是这些点的最大和最小的横坐标和纵坐标。

因为交点的数量级在 $O(n^{2})$，所以不能完全处理所有交点。

所以我们要尽量先排除肯定对结果没影响的点，把可能对结果有影响的点留下来，再统计答案。

排除对结果没影响的点的算法

(1) 考虑没有任何两条直线平行的情况

将直线按斜率排序，排成环形，设直线为 $L_{1}, L_{2}, …, L_{n}$。则只有相邻直线 $L_{i}, L_{i+1}$(包括 $L_{n}$ 与 $L_{1}$)的交点对结果有影响，这样的交点共有 $O(n)$ 个，然后再统计答案。故总的复杂度为 $O(n)$。证明如下

首先只有凸包上的点是对答案有影响的点。例如下图中点 a, b, c 就是凸包上的三个点。

然后考虑组成凸包的每条线段，这些线段只有两种情况: (1) 此线段属于原有直线中的某一条(例如上图中的bc), (2) 此线段不属于任何一条原有直线(例如上图中的ab)。而所有的交点都在这条线段的同一侧, 也可以恰好在这线段上。

  • (1) 对于属于某一条原有直线(记为 $\Phi$)的凸包线段(记为*)：因为所有交点都在直线$\Phi$同一侧或就在线段*上，所以所有直线在$\Phi$的另一侧是呈发散的形状的，见下图。因此凸包线段*的两个端点 a 和点 b，一定是该直线 $\Phi$ 与斜率与该直线 $\Phi$ 最接近的两条直线的交点，否则在 $\Phi$ 的另一侧就会出现另一个交点，那线段 * 就不是凸包线段了。

  • (2) 对于不属于任意一条原有直线的凸包线段(记为*)：线段 * 的两个端点 a 和 b 一定是某两条直线的交点，而这两条直线一定也是斜率相邻的。否则，若有一条直线的斜率在两者之间，则一定会在另一侧出现一个交点，* 就不是凸包线段了。如下图，a 是两条相邻斜率直线的交点，b 是两条相邻斜率直线的交点(虽然有三条，但是多的那条可以忽略)

(2) 有平行直线的情况

对于一组平行直线，只需考虑最外侧的两条。没有平行直线的算法中，的一条直线最多变成两条线，于是原来的一个需要考虑的交点最多变成四个交点，点数依然是 $O(n)$。

综上，完整算法如下:

1
2
3
1. 将所有直线按斜率分桶，每个桶内保留截距最大和最小的两条
2. 枚举每一对相邻斜率的桶，求两个桶中每对直线的交点
3. 对这些交点遍历一遍统计答案

求直线对的交点的算法

给定两个直线求交点，若交点不存在，则返回 false。算法如下：

首先将两条直线写成有向直线的形式 $\vec{a} + p \cdot \vec{b}$ 和 $\vec{c} + q \cdot \vec{d}$。

解方程 $\vec{a} + p \cdot \vec{b} = \vec{c} + q \cdot \vec{d}$。求出 p 之后可以求出两条直线的交点。

按横纵坐标的形式表示出来，联立

求解 p:

注意分母为零的情况：两个方向向量 $\vec{b}$ 和 $\vec{d}$ 平行，这种情况返回 false。

代码 (C++)

在比赛时候为了省时间直接用了模板，模板中的直线是点加方向向量的形式(有向直线)。模板代码如下(其中 Line 和 Vector 也是模板):

1
2
3
4
5
6
7
8
9
10
11
12
13
// 直线与直线相交
bool line_intersection(const Line& l1, const Line& l2, Vector2& x)
{
    double det = l1.b.cross(l2.b); // 两个方向向量的外积
    // 平行或重叠返回false
    if(fabs(det) < EPS)
        return false;
    // 两条有向直线的交点
    Vector2 u = l1.a - l2.a;
    double t = l2.b.cross(u) / det;
    x = l1.a + l1.b * t;
    return true;
}

Line 是有向直线的模板(点加方向向量的形式): $\vec{a} + p \cdot \vec{b}$。模板代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Line
{
    // line: a+pb, a 是点, b 是方向向量
    Vector2 a;
    Vector2 b;
    double deg; // 极角
    Line(Vector2 a, Vector2 b):a(a),b(b)
    {
        deg = b.polar();
    }
    bool operator<(const Line& l) const
    {
        // 方向向量的极角序
        return deg < l.deg;
    }
};

Vector2 是二维向量的模板，实现了向量的加减、数乘、内积、外积、归一化、极角等常见操作。点和方向向量均以二维向量定义，代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// 二维向量的模板
struct Vector2
{
    double x, y;
    explicit Vector2(double x_=0, double y_=0):x(x_),y(y_){}

    // 比较两个向量
    bool operator==(const Vector2& vec) const
    {
        return fabs(x - vec.x) < EPS && fabs(y - vec.y) < EPS;
    }
    bool operator<(const Vector2& vec) const
    {
        if(fabs(x - vec.x) < EPS)
            return y < vec.y;
        return x < vec.x;
    }

    // 向量的加法和减法
    Vector2 operator+(const Vector2& vec) const
    {
        return Vector2(x + vec.x, y + vec.y);
    }
    Vector2 operator-(const Vector2& vec) const
    {
        return Vector2(x - vec.x, y - vec.y);
    }

    // 向量的数乘
    Vector2 operator*(double a) const
    {
        return Vector2(x * a, y * a);
    }

    // 向量的模
    double norm() const
    {
        return hypot(x, y);
    }

    // 返回方向相同的单位向量
    // 零向量不可调用
    Vector2 normalize() const
    {
        return Vector2(x / norm(), y / norm());
    }

    // 从 x 轴正方向转到当前向量的角度
    double polar() const
    {
        // atan2 返回 (-PI, PI]，修正为 [0，2PI)
        // fmod 求两个实数相除的余数
        return fmod(atan2(y, x) + 2 * PI, 2 * PI);
    }

    // 内积
    double dot(const Vector2& vec) const
    {
        return x * vec.x + y * vec.y;
    }
    double cross(const Vector2& vec) const
    {
        return x * vec.y - y * vec.x;
    }

    // 当前向量映射到另一向量的结果
    // vec的长度需要大于0
    Vector2 project(const Vector2& vec) const
    {
        Vector2 r = vec.normalize();
        return r * r.dot(*this);
    }

    // 两个向量的夹角
    // 两个向量长度均需要大于 0
    double insersection_angle(const Vector2& vec) const
    {
        return acos(dot(vec) / norm() * vec.norm());
    }

    // 判断两个向量是否垂直
    // 两个向量长度均需要大于 0
    bool perpendicular(const Vector2& vec) const
    {
        return fabs(dot(vec)) < EPS;
    }

    // 平行四边形面积
    double parallelogram_area(const Vector2& vec) const
    {
        return fabs(cross(vec));
    }

    // 三角形面积，可以扩找到多边形
    double triangle_area(const Vector2& vec) const
    {
        return fabs(cross(vec)) / 2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
const double PI = 2.0 * acos(0.0);
const double EPS = 1e-10;

// 二维向量的模板
struct Vector2;

// 点+方向向量形式的直线的模板
struct Line;

// 点 + 方向向量形式的两条直线求交点的模板
bool line_intersection(const Line& l1, const Line& l2, Vector2& x);

class Solution {
public:
    double minRecSize(vector<vector<int>>& lines_) {
        int n = lines_.size();
        if(n <= 2)
            return 0;
        // 按斜率分桶，并用 map 维护升序，桶内是从小到大的截距
        map<int, set<int>> mapping;
        for(const vector<int>& l: lines_)
            mapping[l[0]].insert(l[1]);
        // 每个斜率取最大和最小的截距构造线段，并按 map 中的顺序(也就是斜率从小到大的顺序)保存在 vector 中
        vector<vector<Line>> lines;
        auto it = mapping.begin();
        while(it != mapping.end())
        {
            // 遇到了新的斜率，需要新分配该斜率的桶
            lines.push_back({});
            Vector2 b(1, it -> first); // 方向向量
            Vector2 a(0, *(it -> second).begin()); // 截距点
            lines.back().emplace_back(a, b);
            if((it -> second).size() > 1)
            {
                Vector2 b2(1, it -> first); // 方向向量
                Vector2 a2(0, *(it -> second).rbegin()); // 截距点
                lines.back().emplace_back(a2, b2);
            }
            ++it;
        }
        if(lines.size() < 2) // 所有直线只有一种斜率不会有交点
            return 0;

        vector<Vector2> points; // 在桶中所有相邻斜率的直线形成的交点
        for(int i = 0; i < (int)lines.size(); ++i)
        {
            int j = (i + 1) % (int)lines.size();
            // lines[i] 为当前斜率对应的一条或两条需要考虑的直线
            // lines[j] 为相邻的下一个斜率对应的一条或两条需要考虑的直线
            for(Line l1: lines[i])
                for(Line l2: lines[j])
                {
                    Vector2 x(-1e9, -1e9);
                    if(line_intersection(l1, l2, x))
                        points.push_back(x);
                }
        }

        // 统计答案
        double min_x = points[0].x;
        double min_y = points[0].y;
        double max_x = points[0].x;
        double max_y = points[0].y;
        for(Vector2 p: points)
        {
            min_x = min(min_x, p.x);
            min_y = min(min_y, p.y);
            max_x = max(max_x, p.x);
            max_y = max(max_y, p.y);
        }
        if(abs(max_x - min_x) < EPS)
            return 0;
        if(abs(max_y - min_y) < EPS)
            return 0;
        double ans = abs(max_x - min_x) * abs(max_y - min_y);
        return ans;
    }
};
Share