比赛 SYOI 专题 5:扫描线 评测结果 EEEEEEEEEE
题目名称 亚特兰蒂斯 最终得分 0
用户昵称 郑霁桓 运行时间 1.415 s
代码语言 C++ 内存使用 15.03 MiB
提交时间 2024-04-23 21:45:41
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,m,ap,as,lp,rp,pp,b[20005],t;
long long ll[20005],rr[20005],l[20005],tp[20005];
double w,x,y,z;
struct N{
    double xx,yy,yp;
    long long sm;
}a[20005];
bool cp(N xx,N yy){
    return xx.xx<yy.xx;
}
void B(long long l,long long r,long long p){
    ll[p]=l,rr[p]=r;
    if(l==r){
        return;
    }
    long long md;
    md=(l+r)/2;
    B(l,md,p*2);
    B(md+1,r,p*2+1);
    return;
}
void pup(long long p){
    if(tp[p]!=0){
        l[p]=b[rr[p]+1]-b[ll[p]];
        return;
    }
    if(ll[p]==rr[p]){
        l[p]=0;
        return;
    }
    l[p]=l[p*2]+l[p*2+1];
    return;
}
void UP(long long l,long long r,long long v,long long p){
    if(ll[p]>r||rr[p]<l){
        return;
    }
    if(ll[p]>=l&&rr[p]<=r){
        tp[p]+=v;
        pup(p);
        return;
    }
    if(ll[p]==rr[p]){
        return;
    }
    long long md;
    md=(l+r)/2;
    if(l<=md){
        UP(l,md,v,p*2);
    }
    if(r>=md){
        UP(md+1,r,v,p*2+1);
    }
    pup(p);
    return;
}
int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    while(cin>>n){
        as=ap=0;
        if(n==0){
            return 0;
        }
        for(int i=1;i<=n;i++){
            cin>>w>>x>>y>>z;
            a[++ap]={w,x,z,1};
            b[ap]=x;
            a[++ap]={y,x,z,-1};
            b[ap]=z;            
        }
        sort(a+1,a+ap+1,cp);
        sort(b+1,b+ap+1);
        t=unique(b+1,b+ap+1)-b-1;
        B(1,t-1,1);
        for(int i=1;i<=ap;i++){
            as+=(a[i].xx-a[i-1].xx)*l[1];
            lp=lower_bound(b+1,b+ap+1,a[i].yy)-b;
            rp=lower_bound(b+1,b+ap+1,a[i].yp)-b;
            UP(lp,rp-1,a[i].sm,1);
        }
        pp++;
        cout<<"Test case #"<<pp<<endl;
        cout<<"Total explored area: "<<fixed<<setprecision(2)<<as<<endl;
    }
    return 0;
}