原问题
问题描述
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.
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 i 1 , y i 1 , x i 2 , y i 2 x_{i1}, y_{i1}, x_{i2}, y_{i2} xi1,yi1,xi2,yi2 <= 1 0 9 10^9 109
题解
思路
- 将矩形拆成与y轴垂直的两条边,按照x轴排序,同时记录边的下标,是否为左边。
- 扫描线:从左向右扫描,遇到左边则加入对应矩形下标,遇到右边则移除下标。
- 扫描完成当前一批x相同的边后,存储并压缩y轴边界,存入vector cal中。
- 下一次迭代时,根据扫描线走过的长度和cal中存储的y轴边界,叠加计算结果。
- 重复上述步骤,直至完成。
代码
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;
}
};
本文含有隐藏内容,请 开通VIP 后查看