扫描线例题——850. Rectangle Area II

原问题

问题描述

原链接

You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.

Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.

Return the total area. Since the answer may be too large, return it modulo 109 + 7.

示例

Example 1

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.
1
2
3
4
5

Example 2

Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 1018 modulo (109 + 7), which is 49.

Constraints

• 1 <= rectangles.length <= 200
• rectanges[i].length == 4
• 0 <= $x_{i1},y_{i1},x_{i2},y_{i2}$ <= $10^9$

题解

思路

1. 将矩形拆成与y轴垂直的两条边，按照x轴排序，同时记录边的下标，是否为左边。
2. 扫描线：从左向右扫描，遇到左边则加入对应矩形下标，遇到右边则移除下标。
3. 扫描完成当前一批x相同的边后，存储并压缩y轴边界，存入vector cal中。
4. 下一次迭代时，根据扫描线走过的长度和cal中存储的y轴边界，叠加计算结果。
5. 重复上述步骤，直至完成。

代码

bool cmp(tuple<int, int, bool> a, tuple<int, int, bool> b) {
    return get<0>(a) < get<0>(b);
}

class Solution {
public:
    const int mod = 1e9 + 7;
    bool vis[201];
    int rectangleArea(vector<vector<int>>& rectangles) {
        //x index isLeft
        vector<tuple<int, int,bool>> edges;
        vector<tuple<int, int>> hs,cal;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < rectangles.size(); ++i) {
            edges.emplace_back(rectangles[i][0],i,true);
            edges.emplace_back(rectangles[i][2],i,false);
        }
        sort(edges.begin(), edges.end(), cmp);
        int edgesLen = edges.size(),  cur = 0, lastX= 0,curVal,sum=0;
        while (cur < edgesLen) {       
            curVal = get<0>(edges[cur]);
            while (cur < edgesLen&& get<0>(edges[cur]) == curVal) {
                if (get<2>(edges[cur])) { //left edge
                    vis[get<1>(edges[cur])] = true; //add this edge
                }
                else { //right edge
                    vis[get<1>(edges[cur])] = false; //remove this edge
                }
                ++cur;
            }
            for (tuple<int, int> t : cal) {
                sum = ((long long)(get<0>(edges[cur-1]) - lastX) * (long long)(get<1>(t) - get<0>(t)) % mod + sum % mod) % mod;
            }
            lastX = get<0>(edges[cur-1]);
            hs.clear(); 
            cal.clear();
            for (int i = 0; i < edgesLen / 2;i++) {
                if (vis[i]) {
                    hs.emplace_back(rectangles[i][1], rectangles[i][3]);
                }
            }
            sort(hs.begin(), hs.end());
            cal.emplace_back(-1, -1);
            for (tuple<int,int> t:hs) {
                if (get<0>(t) > get<1>(cal.back())) {
                    cal.push_back(t);
                }
                else{
                    get<1>(cal.back()) = max(get<1>(cal.back()), get<1>(t));
                }
            }
        }
        return sum;
    }
};
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