• <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>
            算法學社
            記錄難忘的征途
            posts - 141,comments - 220,trackbacks - 0

            題目描述:

                給出很多矩形,求矩形并的面積。

            吐槽:

                1. 經過傻崽大神的教誨,我決定不再向以前那樣惡意縮短代碼了
                2. 看來.... 要慢慢改...
                3. 思路仍然是按照傻崽大神的blog寫的... 然后轉成了zkw版線段樹...

            思路分析:

                離散化之后,在腦海中想像一個掃描線,按照y軸從小到大的順序掃過去。
                掃到的肯定是一個x軸的區間集合。 如果遇到了“新邊”就加到集合中,遇到“舊邊”就從集合中減去,每一次需要這樣操作的時候我們就稱之為“事件點”。
                每次遇到事件點的時候,我們就計算一次面積。就是與下個事件點的y的距離乘以這個區間集合的總長度就可以了。
                那么維護這個集合就可以用線段樹了。
                每次遇到新邊就cnt++,否則就cnt--。如果cnt不為0,說明這個節點有邊覆蓋...
                感覺還是樸素版更容易理解一些,寫起來很飄逸~
            #include<iostream>
            #include<cstdio>
            #include<cassert>
            #include<algorithm>
            using namespace std;
            const int V = 400;
            int M,len;
            struct segment_tree{
                int cnt; double sum;
            } seg[V<<2];
            struct segment{
                double l,r,y; int flag;
                segment(double x1=0,double x2=0,double y1=0,int p=0):l(x1),r(x2),y(y1),flag(p){}
            } num[V];
            bool operator < (segment a,segment b){
                return a.y< b.y;
            }
            double X[V],sum[V<<2];
            inline void upt(int x){
                if(seg[x].cnt) seg[x].sum = sum[x];
                else if(x<M) seg[x].sum = seg[x<<1].sum+seg[x<<1|1].sum;
                else seg[x].sum=0;
            }
            double insert(int l,int r,int p){
            //    cout<<l<<" "<<r<<" "<<p<<endl;
                for(l = l+M, r = r+M+2; l^r^1 ; l>>=1 , r>>=1){
                    if(l&1^1){ seg[l^1].cnt += p; upt(l^1); }
                    if(r&1){ seg[r^1].cnt += p; upt(r^1); }
                    upt(l);upt(r);
                }
                upt(r);
                while(l){
                    upt(l);    l >>=1;
                }
            //    cout<<seg[1].sum<<endl;
                return seg[1].sum;
            }
            int search(double val){
                int l = 0, r = len;
                while(l<r){
                    int mid = l+r >>1;
                    if(X[mid]>= val) r = mid;
                    else l = mid+1;
                }
                return r;
            }
            void build_tree(int n){
                for(int i=0;i<30;i++) if((1<<i) > n+1) {
                        M = 1<<i; break;
                }
                for(int i=0;i<M*2;i++) sum[i] = seg[i].cnt = seg[i].sum = 0;
                for(int i=0;i<n-1;i++) sum[i+M+1] = X[i+1]-X[i];
                for(int i=M-1;i;i--) sum[i] = sum[i<<1]+sum[i<<1|1];
            }
            int main(){
                int n,__test=1;
                while(scanf("%d",&n)!=-1 && n){
                    double x1,y1,x2,y2;
                    int N = 0;
                    for(int i =0 ;i<n;i++){
                        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
                        X[N] = x1;
                        num[N++] = segment(x1,x2,y1,1);
                        X[N] = x2;
                        num[N++] = segment(x1,x2,y2,-1);
                    }
                    sort(X,X+N);
                    sort(num,num+N);
                    len = 1;
                    for(int i=1;i<N;i++){    
                        if(X[i]!=X[i-1]) X[len++] = X[i];
                    }
                    build_tree(len);
                    double ans = 0;
                    for(int i=0;i<N-1;i++){
                        int l = search(num[i].l);
                        int r = search(num[i].r)-1;
                        ans += insert(l,r,num[i].flag) * (num[i+1].y - num[i].y);
            //            cout<<ans<<endl;
                    }
            //        cout<<ans<<endl;
                    printf("Test case #%d\nTotal explored area: %.2lf\n\n",__test++, ans);
                }
                return 0;
            }
            posted on 2012-05-08 16:49 西月弦 閱讀(739) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告經典題目
            久久夜色精品国产亚洲| 综合久久一区二区三区| 久久水蜜桃亚洲av无码精品麻豆| 久久精品国产男包| 国产精品久久久久久福利漫画 | 久久91精品国产91久久麻豆| 久久精品无码专区免费东京热| 午夜精品久久久久久99热| 久久99热国产这有精品| 午夜精品久久久久久| 99久久婷婷国产综合亚洲| 色欲综合久久躁天天躁| 国产亚洲欧美成人久久片| 欧美日韩久久中文字幕| 久久综合中文字幕| 久久精品无码专区免费东京热 | 品成人欧美大片久久国产欧美... 品成人欧美大片久久国产欧美 | 久久一区二区三区免费| 久久99国产综合精品女同| 久久久久久久亚洲精品| 久久精品国产91久久麻豆自制 | 久久AV高清无码| 久久久久青草线蕉综合超碰| 99久久婷婷国产综合精品草原| 无码人妻久久一区二区三区免费丨| 久久99精品久久久久久不卡 | 久久久久综合中文字幕 | 欧美日韩久久中文字幕| 久久久青草青青国产亚洲免观| 国产精品久久久久9999| 精品久久久久久无码专区| 伊人久久大香线蕉亚洲| 久久精品综合网| 欧美亚洲国产精品久久高清| 无码八A片人妻少妇久久| 久久天天躁狠狠躁夜夜不卡| 国产毛片久久久久久国产毛片| 精品久久久久久久久中文字幕| 久久天堂AV综合合色蜜桃网| 久久久久女人精品毛片| 精品熟女少妇a∨免费久久|