力扣每日一题:850:矩形面积II
用到扫描线
class Solution {
public:
typedef long long LL;
typedef pair<int, int> PII;
LL get_area(int l, int r, vector<vector<int>>& rect){
vector<PII> q;
int n = rect.size();
for(int i = 0; i < n; i++){
if(rect[i][0] <= l && rect[i][2] >= r){
LL maxv = max(rect[i][1], rect[i][3]);
LL minv = min(rect[i][1], rect[i][3]);
q.push_back({minv, maxv});
}
}
if(q.size() == 0) return 0;
//合并区间
int len = 0;
sort(q.begin(), q.end());
int st = q[0].first, ed = q[0].second;
for(int i = 1; i < q.size(); i++){
if(q[i].first <= ed){
ed = max(ed, q[i].second);
}
else{
len += ed - st;
st = q[i].first, ed = q[i].second;
}
}
//最后一段加入
len += ed - st;
return 1LL* (r - l) * len;
}
int rectangleArea(vector<vector<int>>& rectangles) {
int mod = 1e9 + 7;
LL ans = 0;
int n = rectangles.size();
vector<int> a;
for(int i = 0; i < n; i++) {
a.push_back(rectangles[i][0]);
a.push_back(rectangles[i][2]);
}
sort(a.begin(), a.end());
int cn = a.size();
for(int i = 0; i < cn - 1; i++) {
ans = (ans + get_area(a[i], a[i + 1], rectangles)) % mod;
}
return ans;
}
};