比赛 |
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;
}