矩形面积求并 扫描线 + 过不去

Code:

#include<cstdio>
#include<algorithm>
#include<string>    
#define maxn 1030000 
#define inf 300000 
#define ll long long 
using namespace std;
void setIO(string s)
{
    string in=s+".in"; 
    freopen(in.c_str(),"r",stdin); 
}
double Arr[maxn];     
namespace tr
{
    #define mid ((l+r)>>1)
    #define lson t[x].l
    #define rson t[x].r  
    struct Node
    {
        int l,r,sum;
        double len; 
    }t[maxn<<2];  
    int tot; 
    int newnode(){ return ++tot; }
    void pushup(int x,int l,int r)
    {
        if(t[x].sum)
        {
            t[x].len=Arr[r]-Arr[l-1];                   
        }
        else 
        {
            t[x].len=t[lson].len+t[rson].len; 
        }
    }
    // 应为 > L (左面是开的)                  
    void Update(int &x,int l,int r,int L,int R,int v)
    {
        if(!x) x = newnode(); 
        if(l>=L&&r<=R)
        {
            t[x].sum+=v;   
            pushup(x,l,r); 
            return; 
        }
        if(L<=mid) Update(lson,l,mid,L,R,v); 
        if(R>mid) Update(rson,mid+1,r,L,R,v); 
        pushup(x,l,r); 
    }
    void re()
    {
        for(int i=0;i<=tot;++i) t[tot].l=t[tot].r=t[tot].sum=t[tot].len=0; 
        tot=0; 
    }
}; 
struct Edge
{
    double l,r,h;   
    int L,R;                   
    int flag; 
}edges[maxn]; 
bool cmp(Edge a,Edge b)
{
    return a.h==b.h?a.flag>b.flag:a.h<b.h;         
}
int i,j,n,root,ed,cc,dd; 
double ans=0.00,a,b,c,d;   
int main()
{
   //  setIO("input");  
    for(int cas=1;;++cas)
    {
        scanf("%d",&n);  
        if(!n) break; 
        ed=root=cc=0;       
        ans=0.00;         
        for(i=1;i<=n;++i)
        {
            scanf("%lf%lf%lf%lf",&a,&b,&c,&d); 
            edges[++ed].l=a,edges[ed].r=c,edges[ed].h=b,edges[ed].flag=1; 
            edges[++ed].l=a,edges[ed].r=c,edges[ed].h=d,edges[ed].flag=-1;                 
            Arr[++cc]=a, Arr[++cc]=c;      
        } 
        sort(edges+1,edges+1+ed,cmp);   
        sort(Arr+1,Arr+1+cc);    
        dd=unique(Arr+1,Arr+cc+1)-(Arr+1); 
        for(i=1;i<=ed;++i)
        {
            edges[i].L=lower_bound(Arr+1,Arr+1+dd,edges[i].l)-Arr; 
            edges[i].R=lower_bound(Arr+1,Arr+1+dd,edges[i].r)-Arr; 
        }
        for(i=1;i<ed;++i)
        {  
            tr::Update(root,0,inf,edges[i].L+1,edges[i].R,edges[i].flag);          
            ans+=(double)(tr::t[root].len)*(edges[i+1].h-edges[i].h);           
        }
        printf("Test case #%d
",cas); 
        printf("Total explored area: %.2f
",ans); 
        printf("
"); 
        tr::re(); 
    }
    return 0; 
}