题目链接
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;}
};
