Luobuyu's Blog

0%

391. 完美矩形

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 7.9k 阅读时长 ≈ 7 分钟
使用经典扫描线解决，注意叶子节点表示的是区间。

391.完美矩形

题目描述：

给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。

如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。

数据范围：

$1\le rects.len \le 2\times 10^4;-10^5\le x_i,y_i,a_i,b_i \le 10^5$

题解：

常规扫描线做法：

使用扫描线求面积并集 $s1$ ，统计所有矩形面积 $s2$ ，统计包围盒面积 $s3$ 。只有三者都相等时才会是精准覆盖。

创建扫描线，假设创建竖着的扫描线，使用四元组(x, y1, y2, flag)。其中 $flag = 1$ 代表入边， $flag = -1$ 代表出边。然后对所有的扫描线进行排序。

每次遇到一根线就对线段树区间进行更新。线段树叶子节点 $(x,x)$ 需要表示区间 $[x, x + 1]$ 。因此对于所有的坐标 $[1, tot]$ ，只需要 $[1,tot-1]$ 。而且空间需要开 $8$ 倍空间，因为每个多边形有两个 $y$ 值。

注意，pushup 函数里面需要特判叶子节点，否则的话下标会越界。

常规线段树做法：

可以直接使用线段树维护区间加和区间和。每次区间加 $1$ 之前，判断一下当前区间是否是空的，否则直接返回 false。

另一种扫描线做法：

对于每一个 $x$ 相等的地方，收集所有的入边和出边，对入边和出边合并线段，如果线段存在覆盖直接返回 false。然后判断最后合并出来的线段是否一样。

对第一条和最后一条需要特判，这两条只有出边或入边。

代码：

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
100
101
102
103
104
struct Line
{
    int x, y1, y2, flag;
    bool operator<(const Line &p) const
    {
        return x < p.x;
    }
};

struct SegTree
{
    struct TreeNode
    {
        int l, r;
        int lazy, sum;
    };
    vector<TreeNode> tree;
    vector<int> &yy;
    SegTree(int n, vector<int> &_yy) : tree(n << 2), yy(_yy)
    {
    }
    void build(int cur, int l, int r)
    {
        tree[cur].l = l, tree[cur].r = r;
        tree[cur].lazy = 0, tree[cur].sum = 0;
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(cur << 1, l, mid);
        build(cur << 1 | 1, mid + 1, r);
    }
    void update(int cur, int l, int r, int k)
    {
        if (l <= tree[cur].l && tree[cur].r <= r)
        {
            tree[cur].lazy += k;
            pushup(cur);
            return;
        }
        int mid = (tree[cur].l + tree[cur].r) >> 1;
        if (l <= mid)
            update(cur << 1, l, r, k);
        if (mid + 1 <= r)
            update(cur << 1 | 1, l, r, k);
        pushup(cur);
    }
    void pushup(int cur)
    {
        if (tree[cur].lazy)
            tree[cur].sum = yy[tree[cur].r + 1] - yy[tree[cur].l];
        else if (tree[cur].l == tree[cur].r)
            tree[cur].sum = 0;
        else
            tree[cur].sum = tree[cur << 1].sum + tree[cur << 1 | 1].sum;
    }
};

class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    vector<Line> line;
    vector<int> yy;
    bool isRectangleCover(vector<vector<int>> &rectangles)
    {
        int n = rectangles.size();
        line.resize(n * 2);
        yy.resize(n * 2);
        long long area = 0;
        int minx1 = INF, miny1 = INF, maxx2 = -INF, maxy2 = -INF;
        for (int i = 0; i < n; ++i)
        {
            auto &rect = rectangles[i];
            int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
            line[i * 2] = {x1, y1, y2, 1};
            line[i * 2 + 1] = {x2, y1, y2, -1};
            yy[i * 2] = y1;
            yy[i * 2 + 1] = y2;
            area += (x2 - x1) * 1ll * (y2 - y1);
            minx1 = min(minx1, x1);
            miny1 = min(miny1, y1);
            maxx2 = max(maxx2, x2);
            maxy2 = max(maxy2, y2);
        }
        yy.emplace_back(-INF);
        sort(yy.begin(), yy.end());
        int tot = unique(yy.begin(), yy.end()) - yy.begin() - 1;
        sort(line.begin(), line.end());
        SegTree segTree(tot, yy);
        segTree.build(1, 1, tot - 1);
        long long area_union = 0;
        for (int i = 0; i < n * 2 - 1; ++i)
        {
            int y1 = lower_bound(yy.begin() + 1, yy.begin() + tot + 1, line[i].y1) - yy.begin();
            int y2 = lower_bound(yy.begin() + 1, yy.begin() + tot + 1, line[i].y2) - yy.begin();
            segTree.update(1, y1, y2 - 1, line[i].flag);
            area_union += segTree.tree[1].sum * 1ll * (line[i + 1].x - line[i].x);
        }
        long long area_rect = (maxx2 - minx1) * 1ll * (maxy2 - miny1);
        return area_union == area && area_union == area_rect;
    }
};
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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
struct Line
{
    int x, y1, y2, flag;
    bool operator<(const Line &p) const
    {
        return x != p.x ? x < p.x : y1 < p.y1;
    }
};
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    vector<Line> line;
    bool isRectangleCover(vector<vector<int>> &rectangles)
    {
        int n = rectangles.size();
        line.resize(n * 2);
        long long area = 0;
        int minx1 = INF, miny1 = INF, maxx2 = -INF, maxy2 = -INF;
        for (int i = 0; i < n; ++i)
        {
            auto &rect = rectangles[i];
            int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
            line[i * 2] = {x1, y1, y2, 1};
            line[i * 2 + 1] = {x2, y1, y2, -1};
            area += (x2 - x1) * 1ll * (y2 - y1);
            minx1 = min(minx1, x1);
            miny1 = min(miny1, y1);
            maxx2 = max(maxx2, x2);
            maxy2 = max(maxy2, y2);
        }
        int l = 0;
        n <<= 1;
        sort(line.begin(), line.end());
        while (l < n)
        {
            int r = l;
            while (r + 1 < n && line[r + 1].x == line[l].x)
                ++r;
            vector<pair<int, int>> left, right;
            for (int i = l; i <= r; ++i)
            {
                auto &v = (line[i].flag == 1 ? left : right);
                if (!v.size())
                {
                    v.emplace_back(line[i].y1, line[i].y2);
                }
                else
                {
                    int &pre = v.back().second;
                    if (pre > line[i].y1)
                        return false;
                    else
                        pre = line[i].y2;
                }
            }
            if (l > 0 && r <= n - 2)
            {
                // 不是起始和结束边
                if (left.size() != right.size())
                    return false;

                if (left.front() != right.front())
                    return false;
            }
            else
            {
                if (left.size() + right.size() != 1)
                    return false;
            }
            l = r + 1;
        }
        return true;
    }
};
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
struct Line
{
    int x, y1, y2, flag;
    bool operator<(const Line &p) const
    {
        return x == p.x ? flag < p.flag : x < p.x;
    }
};

struct SegTree
{
    struct TreeNode
    {
        int l, r;
        int lazy, sum;
    };
    vector<TreeNode> tree;
    vector<int> &yy;
    SegTree(int n, vector<int> &_yy) : tree(n << 2), yy(_yy)
    {
    }
    void build(int cur, int l, int r)
    {
        tree[cur].l = l, tree[cur].r = r;
        tree[cur].lazy = 0, tree[cur].sum = 0;
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(cur << 1, l, mid);
        build(cur << 1 | 1, mid + 1, r);
    }
    void update(int cur, int l, int r, int k)
    {
        if (l <= tree[cur].l && tree[cur].r <= r)
        {
            tree[cur].lazy += k;
            tree[cur].sum += k * (tree[cur].r + 1 - tree[cur].l);
            return;
        }
        int mid = (tree[cur].l + tree[cur].r) >> 1;
        if (tree[cur].lazy)
            pushdown(cur);
        if (l <= mid)
            update(cur << 1, l, r, k);
        if (mid + 1 <= r)
            update(cur << 1 | 1, l, r, k);
        tree[cur].sum = tree[cur << 1].sum + tree[cur << 1 | 1].sum;
    }
    int query(int cur, int l, int r)
    {
        if (l <= tree[cur].l && tree[cur].r <= r)
        {
            return tree[cur].sum;
        }
        if (tree[cur].lazy)
            pushdown(cur);
        int sum = 0;
        int mid = (tree[cur].l + tree[cur].r) >> 1;
        if (l <= mid)
            sum += query(cur << 1, l, r);
        if (mid + 1 <= r)
            sum += query(cur << 1 | 1, l, r);
        return sum;
    }
    void pushdown(int cur)
    {
        tree[cur << 1].lazy += tree[cur].lazy;
        tree[cur << 1].sum += tree[cur].lazy * (tree[cur << 1].r + 1 - tree[cur << 1].l);
        tree[cur << 1 | 1].lazy += tree[cur].lazy;
        tree[cur << 1 | 1].sum += tree[cur].lazy * (tree[cur << 1 | 1].r + 1 - tree[cur << 1 | 1].l);
        tree[cur].lazy = 0;
    }
};

class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    vector<Line> line;
    vector<int> yy;
    bool isRectangleCover(vector<vector<int>> &rectangles)
    {
        int n = rectangles.size();
        line.resize(n * 2);
        yy.resize(n * 2);
        long long area = 0;
        int minx1 = INF, miny1 = INF, maxx2 = -INF, maxy2 = -INF;
        for (int i = 0; i < n; ++i)
        {
            auto &rect = rectangles[i];
            int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
            line[i * 2] = {x1, y1, y2, 1};
            line[i * 2 + 1] = {x2, y1, y2, -1};
            yy[i * 2] = y1;
            yy[i * 2 + 1] = y2;
            area += (x2 - x1) * 1ll * (y2 - y1);
            minx1 = min(minx1, x1);
            miny1 = min(miny1, y1);
            maxx2 = max(maxx2, x2);
            maxy2 = max(maxy2, y2);
        }
        long long area_rect = (maxx2 - minx1) * 1ll * (maxy2 - miny1);
        if (area != area_rect)
            return false;
        yy.emplace_back(-INF);
        sort(yy.begin(), yy.end());
        int tot = unique(yy.begin(), yy.end()) - yy.begin() - 1;
        sort(line.begin(), line.end());
        SegTree segTree(tot, yy);
        segTree.build(1, 1, tot - 1);
        long long area_union = 0;
        for (int i = 0; i < n * 2 - 1; ++i)
        {
            int y1 = lower_bound(yy.begin() + 1, yy.begin() + tot + 1, line[i].y1) - yy.begin();
            int y2 = lower_bound(yy.begin() + 1, yy.begin() + tot + 1, line[i].y2) - yy.begin();
            if (line[i].flag == 1)
            {
                if (segTree.query(1, y1, y2 - 1) != 0)
                    return false;
            }
            segTree.update(1, y1, y2 - 1, line[i].flag);
        }
        return true;
    }
};