yang li mei guo,shi ce quan WA,qiuzhu!
查看原帖
yang li mei guo,shi ce quan WA,qiuzhu!
658786
STUDENT00楼主2022/12/13 17:19

daima:

#include<bits/stdc++.h>
#define N 5005
using namespace std;
int n,ans;
struct Rectangle{
    int x1,y1,x2,y2;
} rs[N];
vector<int> xx,yy;
struct Line{
    int x,f;
    friend bool operator<(const Line a,const Line b){
        return a.x<b.x;
    }
};
vector<Line> ls;
void updatex(int x){
    ls.clear();
    for(int i=1;i<=n;i++){
        if(x>=rs[i].x1&&x<=rs[i].x2){ls.push_back({rs[i].y1,1});ls.push_back({rs[i].y2,-1});}
    }
}
void updatey(int y){
    ls.clear();
    for(int i=1;i<=n;i++){
        if(y>=rs[i].y1&&y<=rs[i].y2){ls.push_back({rs[i].x1,1});ls.push_back({rs[i].x2,-1});}
    }
}
void updatels(){
    for(int i=0;i<ls.size()-1;i++){
        if(ls[i].x==ls[i+1].x){ls[i+1].f+=ls[i].f;ls.erase(ls.begin()+i);}
    }
}
int sum(){
    int s=0,last,ans=0;
    for(int i=0;i<ls.size();i++){
        if(!s) last=i;
        if(!(s+ls[i].f)) ans+=2;
        s+=ls[i].f;
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d%d",&rs[i].x1,&rs[i].y1,&rs[i].x2,&rs[i].y2);
    for(int i=1;i<=n;i++){xx.push_back(rs[i].x1);xx.push_back(rs[i].x2);}
    sort(xx.begin(),xx.end());
    xx.resize(unique(xx.begin(),xx.end())-xx.begin());
    for(int i=0;i<xx.size();i++){
        updatex(xx[i]);
        updatels();
        if(i) ans+=sum()*(xx[i]-xx[i-1]);
    }
    for(int i=1;i<=n;i++){yy.push_back(rs[i].y1);yy.push_back(rs[i].y2);}
    sort(yy.begin(),yy.end());
    yy.resize(unique(yy.begin(),yy.end())-yy.begin());
    for(int i=0;i<yy.size();i++){
        updatey(yy[i]);
        updatels();
        if(i) ans+=sum()*(yy[i]-yy[i-1]);
    }
    printf("%d",ans);
    return 0;
}
2022/12/13 17:19
加载中...