• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-38  評論-23  文章-0  trackbacks-0
            /*
            Author:miyou
            PROG:the perimeter of many rectangles
            LANG:C++
            */

            #include
            <iostream>
            #include
            <vector>
            #include
            <algorithm>
            using namespace std;
            #define MAXN 1000000
            const __int64 mininf=1000000;
            const __int64 maxinf=-1000000;
            struct Line
            {
                __int64 count,len;
            //count 記錄線段覆蓋次數(shù),len 該段線段長度
                __int64 l,r;//線段左右兩端點
                int lbc,rbc;//線段左右兩端點被覆蓋的次數(shù),0表示未被覆蓋
                __int64 nseg;//該線段中連續(xù)線段個數(shù).
            }
            ;
            struct node
            {
                __int64 x,down,up;
            //掃描線,down 線的下端點,up 線的上端點,x掃描線的x位置
                bool flag;//表示是矩形的左邊線還是右邊線
                node(__int64 tx,__int64 td,__int64 tu,bool tf):x(tx),down(td),up(tu),flag(tf)
                
            {
                }

            }
            ;
            __int64 miny,maxy;
            vector
            < node > vec;
            Line Ltree[MAXN];
            bool operator< (const node& a,const node& b)
            {
                
            return a.x<b.x;
            }

            void build(__int64 l,__int64 r,int step)
            {
                Ltree[step].count
            =0;Ltree[step].len=0;
                Ltree[step].lbc
            =false;Ltree[step].rbc=false;
                Ltree[step].nseg
            =0;
                Ltree[step].r
            =r;Ltree[step].l=l;
                
            if(r-l>1)
                
            {
                    build(l,(l
            +r)/2,2*step);
                    build((l
            +r)/2,r,2*step+1);
                }

            }

            void update(int step)
            {
                
            if(Ltree[step].count>0)
                
            {
                    Ltree[step].len
            =Ltree[step].r-Ltree[step].l;
                    Ltree[step].nseg
            =1;
                }

                
            else
                    
            if(Ltree[step].r-Ltree[step].l>1)
                    
            {
                        Ltree[step].len
            =Ltree[2*step].len+Ltree[2*step+1].len;
                        Ltree[step].nseg
            =Ltree[2*step].nseg+Ltree[2*step+1].nseg;
                        
            if(Ltree[step].nseg&&Ltree[2*step].rbc&&Ltree[2*step+1].lbc)
                            Ltree[step].nseg
            --;
                    }

                    
            else
                    
            {
                        Ltree[step].len
            =0;
                        Ltree[step].nseg
            =0;
                    }

            }

            void insert(__int64 l,__int64 r,int step)
            {
                
            if(Ltree[step].l==l) Ltree[step].lbc++;
                
            if(Ltree[step].r==r) Ltree[step].rbc++;
                
            if(l==Ltree[step].l&&Ltree[step].r==r)
                    Ltree[step].count
            ++;
                
            else
                
            {
                    __int64 mid
            =(Ltree[step].l+Ltree[step].r)/2;
                    
            if(r<=mid)
                        insert(l,r,
            2*step);
                    
            else 
                        
            if(l>=mid)
                            insert(l,r,
            2*step+1);
                        
            else
                        
            {
                            insert(l,mid,
            2*step);
                            insert(mid,r,
            2*step+1);
                        }

                }

                update(step);
            }

            void del(__int64 l,__int64 r,int step)
            {
                
            if(Ltree[step].l==l) Ltree[step].lbc--;
                
            if(Ltree[step].r==r) Ltree[step].rbc--;
                
            if(l==Ltree[step].l&&Ltree[step].r==r)
                    Ltree[step].count
            --;
                
            else
                
            {
                    __int64 mid
            =(Ltree[step].l+Ltree[step].r)/2;
                    
            if(r<=mid)
                        del(l,r,
            2*step);
                    
            else 
                        
            if(l>=mid)
                            del(l,r,
            2*step+1);
                        
            else
                        
            {
                            del(l,mid,
            2*step);
                            del(mid,r,
            2*step+1);
                        }

                }

                update(step);
            }


            int main()
            {
                
            int n;
                __int64 x1,x2,y1,y2;
                
            while(scanf("%d",&n)==1)
                
            {
                    miny
            =mininf;
                    maxy
            =maxinf;
                    
            for(int i=0;i<n;i++)
                    
            {
                        scanf(
            "%I64d%I64d%I64d%I64d",&x1,&y1,&x2,&y2);
                        vec.push_back(node(x1,y1,y2,
            true));
                        vec.push_back(node(x2,y1,y2,
            false));
                        miny
            =min(miny,y1);
                        maxy
            =max(maxy,y2);
                    }

                    sort(vec.begin(),vec.end());
                    
            //cout<<miny<<" "<<maxy<<endl;
                    build(miny,maxy,1);
                    __int64 peri
            =0;
                    
            int m=vec.size();
                    __int64 lastlen
            =0,lastseg=0;
                    
            for(int i=0;i<m;i++)
                    
            {
                        
            if(vec[i].flag)
                            insert(vec[i].down,vec[i].up,
            1);
                        
            else
                            del(vec[i].down,vec[i].up,
            1);
                        peri
            +=abs(Ltree[1].len-lastlen);
                        
            //cout<<"len:"<<Ltree[1].len<<endl;
                        lastlen=Ltree[1].len;
                        
            if(i)
                            peri
            +=2*(vec[i].x-vec[i-1].x)*lastseg;
                        lastseg
            =Ltree[1].nseg;
                        
            //cout<<"seg:"<<Ltree[1].nseg<<endl;
                    }

                    printf(
            "%I64d\n",peri);
                }

                
            return 0;
            }



            posted on 2009-05-03 21:02 米游 閱讀(782) 評論(0)  編輯 收藏 引用 所屬分類: ACM
            久久人妻少妇嫩草AV蜜桃| 成人综合久久精品色婷婷| 狠色狠色狠狠色综合久久| 99国产欧美精品久久久蜜芽| 2022年国产精品久久久久| 久久国产精品免费一区二区三区 | 久久精品国产亚洲精品| 综合久久精品色| 99久久国语露脸精品国产| 亚洲第一永久AV网站久久精品男人的天堂AV| 香蕉久久夜色精品国产尤物| 国产国产成人精品久久| 久久综合偷偷噜噜噜色| 99久久精品国产一区二区蜜芽| 99久久精品免费看国产一区二区三区 | 亚洲精品美女久久久久99小说| 久久亚洲国产成人精品性色| 免费一级做a爰片久久毛片潮| 99蜜桃臀久久久欧美精品网站 | 人妻无码久久一区二区三区免费| 日本精品久久久中文字幕| 亚洲国产精品无码久久| 久久免费国产精品| 97精品国产97久久久久久免费| 午夜久久久久久禁播电影| 久久精品一本到99热免费| 久久精品成人免费观看97| 中文字幕一区二区三区久久网站| WWW婷婷AV久久久影片| 亚洲人成精品久久久久| 欧美精品国产综合久久| 亚洲综合久久久| 久久久亚洲AV波多野结衣| 国产精品久久久久久五月尺| 久久综合亚洲色HEZYO国产| 久久精品国产精品亜洲毛片| 国内精品伊人久久久久影院对白| 久久综合综合久久狠狠狠97色88| 久久99免费视频| 很黄很污的网站久久mimi色| 久久九九久精品国产|