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

            題目描述:

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

            吐槽:

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

            思路分析:

                離散化之后,在腦海中想像一個掃描線,按照y軸從小到大的順序掃過去。
                掃到的肯定是一個x軸的區(qū)間集合。 如果遇到了“新邊”就加到集合中,遇到“舊邊”就從集合中減去,每一次需要這樣操作的時候我們就稱之為“事件點”。
                每次遇到事件點的時候,我們就計算一次面積。就是與下個事件點的y的距離乘以這個區(qū)間集合的總長度就可以了。
                那么維護這個集合就可以用線段樹了。
                每次遇到新邊就cnt++,否則就cnt--。如果cnt不為0,說明這個節(jié)點有邊覆蓋...
                感覺還是樸素版更容易理解一些,寫起來很飄逸~
            #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 西月弦 閱讀(768) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告經(jīng)典題目
            一级做a爰片久久毛片16| 中文字幕久久久久人妻| 久久精品无码一区二区三区日韩| 99国内精品久久久久久久| 一本大道久久香蕉成人网| 亚洲国产精品18久久久久久| 91精品国产91久久久久久青草 | 久久久国产乱子伦精品作者| 久久久精品免费国产四虎| 久久狠狠爱亚洲综合影院| 99久久国产亚洲高清观看2024| 亚洲中文精品久久久久久不卡| 99久久精品免费| 69久久夜色精品国产69| 亚洲色大成网站WWW久久九九| 久久久久久噜噜精品免费直播| 久久国产精品77777| 99久久这里只精品国产免费| 久久精品成人免费观看97| 久久午夜电影网| 精品久久久久久国产潘金莲| 国产亚洲精品久久久久秋霞| 久久人人爽人人爽人人片AV高清 | 久久精品无码免费不卡| av午夜福利一片免费看久久| 欧美喷潮久久久XXXXx| 国产色综合久久无码有码| 狠狠综合久久AV一区二区三区 | 综合网日日天干夜夜久久| 亚洲国产精品综合久久一线| 日产久久强奸免费的看| 欧美久久亚洲精品| 亚洲欧美一级久久精品| 中文成人久久久久影院免费观看| 午夜精品久久久久久久无码| 日韩欧美亚洲综合久久| 久久久久亚洲AV无码专区首JN | 久久久久久久久波多野高潮| 久久久久久久波多野结衣高潮| 国产A三级久久精品| 天天爽天天狠久久久综合麻豆|