hdu4052矩形面积并

时间：2022-05-26 04:28:13

建模需要注意下细节，，这是做扫描线的惯例，就是最好把模型建立在笛卡尔坐标系上

剩下的看链接和注释https://blog.csdn.net/shiqi_614/article/details/7983508

/*

扫描线解一个被覆盖了一些面积的区间

问能空余地方能放置多少个1*M或M*1的矩形

设[i,j]为可以作为矩形放置起点的方块，那么只要统计出不能作为起点的方块的面积即可

本题用的是点的行列号，转换成笛卡尔坐标系上的坐标即可

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<map>

#define ll long long

#define maxn 100005

#define lson l,m,rt<<1

#define rson m,r,rt<<1|1

using namespace std;

struct Seg{

    int x,y1,y2,c;

    Seg(){}

    Seg(int a,int b,int c,int d):x(a),y1(b),y2(c),c(d){}

    bool operator<(const Seg & a){return x<a.x;}

}segs[maxn];

map<int,int>mp;

int y[maxn],data[maxn][],tot,toty;

int sum[maxn<<],flag[maxn<<];

void pushup(int rt,int l,int r){

    if(flag[rt]>)

        sum[rt]=y[r]-y[l];

    else {

        if(l+==r) sum[rt]=;

        else sum[rt]=sum[rt<<]+sum[rt<<|];

    }

}

void update(int L,int R,int c,int l,int r,int rt){

    if(L<=l && R>=r){

        flag[rt]+=c;

        pushup(rt,l,r);

        return;

    }

    int m=l+r>>;

    if(L<m) update(L,R,c,lson);

    if(R>m) update(L,R,c,rson);

    pushup(rt,l,r);

}

ll solve(int n,int w,int h,int m){

    memset(y,,sizeof y);

    memset(segs,,sizeof segs);

    memset(sum,,sizeof sum);

    memset(flag,,sizeof flag);

    mp.clear();

    tot=toty=;

    y[toty++]=,y[toty++]=h;

    segs[tot++]=Seg(max(,w-m),,h,);

    segs[tot++]=Seg(w,,h,-);

    for(int i=;i<n;i++){

        int x1=max(,data[i][]-m),y1=data[i][];

        int x2=data[i][],y2=data[i][];

        segs[tot++]=Seg(x1,y1,y2,);

        segs[tot++]=Seg(x2,y1,y2,-);

        y[toty++]=y1;y[toty++]=y2;

    }

    sort(y,y+toty);

    toty=unique(y,y+toty)-y;

    for(int i=;i<toty;i++) mp[y[i]]=i;

    sort(segs,segs+tot);

    ll res=;

    for(int i=;i<tot;i++){

        if(i!=) res+=(ll)(segs[i].x-segs[i-].x)*sum[];

        update(mp[segs[i].y1],mp[segs[i].y2],segs[i].c,,toty-,);

//    cout << res<<endl;

    }

//    cout << res << endl <<endl;

    return res;

}

int main(){

    int w,h,n,m;

    while(scanf("%d%d%d%d",&w,&h,&n,&m)==){

        for(int i=;i<n;i++)

            for(int j=;j<;j++){

                scanf("%d",&data[i][j]);

                if(j==||j==)data[i][j]++;

            }

        ll res1=(ll)(w*h)-solve(n,w+,h+,m-);//把点行列号转换成笛卡尔坐标，即把点扩展成一块单位面积

        for(int i=;i<n;i++){//对换矩形的xy轴坐标

            swap(data[i][],data[i][]);

            swap(data[i][],data[i][]);

        }

        ll res2=(ll)(w*h)-solve(n,h+,w+,m-);

           //cout << res1 << " " << res2 << endl;

        if(m!=) printf("%lld\n",res1+res2);

        else printf("%lld\n",res1);//注意这个细节

    }

    return ;

}

相关文章