注意区间是左闭右开的qwq

扫描线使用线段树来维护x轴的,把其分成一个一个的区间

#include<bits/stdc++.h>
#define maxn 105
using namespace std;
struct node{
    int kind;
    double l,r,h;
    node (){}
    node(double a,double b,double c,int d):l(a),r(b),h(c),kind(d){}
    friend bool operator<(node a,node b){
        return a.h<b.h;
    } 
}nd[maxn];
int n,lc[maxn*2],rc[maxn*2],add[maxn*2],cae=0,rt,npp=0;
double a,b,c,d,ans,x[maxn],sum[maxn*2];
void build(int &now,int l,int r){
     now=++npp;
     if(l==r) return;
     int m=l+r>>1;
     build(lc[now],l,m);
     build(rc[now],m+1,r);
}
void upload(int now,int l,int r){
    if(add[now]) sum[now]=x[r+1]-x[l];//左开右闭
    else if(l==r) sum[now]=0;
    else  sum[now]=sum[lc[now]]+sum[rc[now]]; 
}
void update(int now,int l,int r,int x,int y,int ss){
    if(l>=x&&r<=y){
        add[now]+=ss;
        upload(now,l,r);
        return;
    }
    int m=l+r>>1;
    if(y<=m) update(lc[now],l,m,x,y,ss);
    else if(x>m) update(rc[now],m+1,r,x,y,ss);
    else {
        update(lc[now],l,m,x,y,ss);
        update(rc[now],m+1,r,x,y,ss);
    }
    
    upload(now,l,r);
}
void init(){
    int np=0;
    npp=0;
    ans=0;
    for(int i=1;i<=n;i++){
        scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
        x[++np]=a;nd[np]=node(a,c,b,1);
        x[++np]=c;nd[np]=node(a,c,d,-1);
    }
    sort(x+1,x+np+1);
    sort(nd+1,nd+np+1);
    int cnt=unique(x+1,x+np+1)-x-1;
    build(rt,1,cnt);
    memset(add,0,sizeof(add));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=np;i++){
        int l=lower_bound(x+1,x+cnt+1,nd[i].l)-x;
        int r=lower_bound(x+1,x+cnt+1,nd[i].r)-x-1;//左闭右开
        update(rt,1,cnt,l,r,nd[i].kind);
        ans+=sum[1]*(nd[i+1].h-nd[i].h); 
    } 
    printf("Test case #%d\nTotal explored area: %.2lf\n\n",cae,ans);
}
int main(){
    while(1){
    cae++;
    scanf("%d",&n);
    if(n==0) break; 
    init();
    }
    
    
    return 0;
}
Last modification:April 5th, 2019 at 08:55 pm