AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 吐槽
  • App
  • 登录/注册

LeetCode 850. 矩形面积 II

作者: 作者的头像   AcJarNinLee ,  2022-09-16 11:41:51 ,  所有人可见 ,  阅读 49


0


扫描线模板 先将竖线(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;
    }
};

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息