# hdu 1828 poj 1177 picture 求周长并

###### 分类 : 博文聚焦 | 发布时间 : 2012-01-27 22:30:00 | 浏览 : 0

View Code
`#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;const int maxn = 22222;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1struct seg{    double l,r,h;    int flag;    seg(){}    seg(double _l,double _r,double _h,int _flag):l(_l),r(_r),h(_h),flag(_flag){}    bool operator < (const seg &cmp) const{        return h<cmp.h;    }}horizontal_seg[maxn];int cover[maxn<<2];bool lbd[maxn<<2],rbd[maxn<<2];int num[maxn<<2];double sum[maxn<<2],x[maxn];void pushup(int rt,int l,int r){    if(cover[rt]){        lbd[rt]=rbd[rt]=true;        sum[rt]=x[r+1]-x[l];        num[rt]=1;        return ;    }    if(l==r){        num[rt]=lbd[rt]=rbd[rt]=sum[rt]=0;        return ;    }    lbd[rt]=lbd[rt<<1];    rbd[rt]=rbd[rt<<1|1];    sum[rt]=sum[rt<<1]+sum[rt<<1|1];    num[rt]=num[rt<<1]+num[rt<<1|1];    if(lbd[rt<<1|1]&&rbd[rt<<1]) num[rt]--;}void update(int L,int R,int c,int l,int r,int rt){    if(L<=l&&r<=R){        cover[rt]+=c;        pushup(rt,l,r);        return ;    }    int m=(l+r)>>1;    if(L<=m) update(L,R,c,lson);    if(R>m) update(L,R,c,rson);    pushup(rt,l,r);}void init(){    memset(sum,0,sizeof(sum));    memset(cover,0,sizeof(cover));    memset(num,0,sizeof(num));    memset(lbd,false,sizeof(lbd));    memset(rbd,false,sizeof(rbd));}int main(){    int n,i,j,tot;    double x1,x2,y1,y2;    while(scanf("%d",&n)!=EOF){        tot=0;        for(i=1;i<=n;i++){            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);            x[tot]=x1;            horizontal_seg[tot++]=seg(x1,x2,y1,1);            x[tot]=x2;            horizontal_seg[tot++]=seg(x1,x2,y2,-1);        }        sort(x,x+tot);        sort(horizontal_seg,horizontal_seg+tot);        int real_tot=unique(x,x+tot)-x;        init();        double pre=0,ans=0;        for(i=0;i<tot;i++){            int left=lower_bound(x,x+real_tot,horizontal_seg[i].l)-x;            int right=lower_bound(x,x+real_tot,horizontal_seg[i].r)-x-1;            update(left,right,horizontal_seg[i].flag,0,real_tot-1,1);            ans+=fabs(sum[1]-pre);            ans+=2*num[1]*(horizontal_seg[i+1].h-horizontal_seg[i].h);            pre=sum[1];        }        printf("%.0lf\n",ans);    }    return 0;}`