codevs3044

codevs3044

题面

大意：给出n个矩形求覆盖的总面积

看了hzwer的blog 似懂非懂 链接

可能还要多练点吧qaq

#include <bits/stdc++.h>

using namespace std;

#define N 10005

int n,m;

struct node{double x1,x2,y; int op;}line[N];

inline bool cmp(node a,node b){return a.y < b.y;}

double hash[N];

struct SegmentTree{int l,r,co; double sum;}Tree[N<<];

inline void pushup(int x)

{

    int l=Tree[x].l,r=Tree[x].r;

    if(Tree[x].co>)Tree[x].sum=hash[r+]-hash[l];

    else if(l==r) Tree[x].sum=;

    else Tree[x].sum=Tree[x<<].sum+Tree[x<<|].sum;

}

inline void build(int l,int r,int x)

{

    Tree[x].l=l; Tree[x].r=r; Tree[x].co=;

    if(l==r){Tree[x].sum=;return;}

    int mid=(l+r)>>; build(l,mid,x<<); build(mid+,r,x<<|); pushup(x);

}

inline void updata(int l,int r,int x,int val)

{

    if(l<=Tree[x].l&&Tree[x].r<=r){ Tree[x].co+=val; pushup(x); return;}

    int mid=(Tree[x].l+Tree[x].r)>>;

    if(l<=mid) updata(l,r,x<<,val); if(r>mid) updata(l,r,x<<|,val); pushup(x);

}

int main()

{

    while(~scanf("%d",&n))

    {

        int i; double x1,y1,x2,y2,ans=; if(n==) break;

        for(i=;i<=n;i++)

        {

            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

            line[i*-].x1=line[i*].x1=x1;

            line[i*-].x2=line[i*].x2=x2;

            line[i*-].y=y1; line[i*-].op=-;

            line[i*].y=y2; line[i*].op=;

            hash[i*-]=x1; hash[i*]=x2;

        }

        n*=; sort(line+,line+n+,cmp); sort(hash+,hash+n+); m=unique(hash+,hash+n+)-hash-; build(,m,);

        for(i=n;i>=;i--)

        {

            int l=lower_bound(hash+,hash+m+,line[i].x1)-hash,r=lower_bound(hash+,hash+m+,line[i].x2)-hash-;

            updata(l,r,,line[i].op); ans+=(line[i].y-line[i-].y)*Tree[].sum;

        }

        printf("%.2lf\n",ans);

    }

}