题目链接
https://leetcode.cn/problems/rectangle-area-ii/
题目大意
题目思路
- 选取连续的x值：(left,right),在这个区间内，沿着x轴的方向扫描，求出所有符合条件的(y1,y2)
- 算出扫描区间的h，结合 w * h，算出面积！
礼貌拿图，多谢三叶姐（https://leetcode.cn/problems/rectangle-area-ii/solutions/1826992/gong-shui-san-xie-by-ac_oier-9r36/）
题目代码
#define ll long long
const int MOD = 1e9 + 7;
class Solution {
public:
int rectangleArea(vector<vector<int>>& rectangles) {
vector<int> x_axis;
for(auto x:rectangles){
x_axis.push_back(x[0]);
x_axis.push_back(x[2]);
}
sort(x_axis.begin(),x_axis.end());
ll ans = 0;
for(int i = 0;i < x_axis.size() - 1;++i){
int left = x_axis[i],right = x_axis[i + 1];
int w = right - left;
if(w == 0) continue;
vector<array<int,2>> y_axis;
for(auto x:rectangles){
if(x[0] <= left && right <= x[2])
y_axis.push_back({x[1],x[3]});
}
sort(y_axis.begin(),y_axis.end());
int h = 0,l = -1,r = -1;
for(auto y:y_axis){
if(y[0] > r){
h += r - l;
l = y[0],r = y[1];
}else if(y[1] > r){
r = y[1];
}
}
h += r - l;
ans = (ans + (ll)w * h) % MOD;
}
return ans;
}
};