扫描线模板 先将竖线(x = t)进行排序, 在对相邻的两根线之间的横线(y = t)进行区间合并同时计算横线所构成矩形的高, 最后每一个矩形用高乘以宽求出面积 最终返回面积之和
typedef pair<int, int> PII;
typedef long long LL;
#define x first
#define y second
LL calc(vector<vector<int>>& rts, int a, int b)
{
vector<PII> q;
for(auto& c : rts)
if(c[0] <= a && c[2] >= b) q.push_back({c[1], c[3]});
sort(q.begin(),q.end());
LL st = -1, ed = -1, res = 0;
for(auto& c : q){
if(ed < c.x){
if(st != -1) res += ed - st;
st = c.x, ed = c.y;
}
else ed = ed > c.y ? ed : c.y;
}
res += ed - st;
return res * (b - a);
}
class Solution {
public:
int rectangleArea(vector<vector<int>>& rts) {
vector<int> a;
for(auto& c : rts){
a.push_back(c[0]);
a.push_back(c[2]);
}
sort(a.begin(), a.end());
LL ans = 0;
for(int i = 1; i < a.size(); i ++){
ans += calc(rts, a[i - 1], a[i]);
}
return ans % 1000000007;
}
};