• <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 西月弦 閱讀(751) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告經典題目
            久久精品国产99久久丝袜| 国产福利电影一区二区三区久久老子无码午夜伦不 | 亚洲国产精品无码久久| 99久久精品免费看国产一区二区三区| 久久夜色精品国产噜噜亚洲a| 日日狠狠久久偷偷色综合96蜜桃 | 亚洲日韩中文无码久久| 久久人人爽人人爽人人片AV不| 久久国产美女免费观看精品| 久久国产综合精品五月天| 国产精品乱码久久久久久软件 | 老司机午夜网站国内精品久久久久久久久 | 一本一道久久a久久精品综合| 午夜精品久久影院蜜桃| 亚洲国产天堂久久综合| 久久无码人妻一区二区三区| 热re99久久精品国产99热| 麻豆av久久av盛宴av| 久久99国产综合精品女同| 亚洲欧洲精品成人久久曰影片| 国产偷久久久精品专区| 亚洲国产精品综合久久网络 | 内射无码专区久久亚洲| 国产精品国色综合久久| 伊人久久大香线蕉综合影院首页| 欧美综合天天夜夜久久| 麻豆亚洲AV永久无码精品久久| 一日本道伊人久久综合影| 日产久久强奸免费的看| 中文字幕久久欲求不满| 国产精品久久久久久久久久影院| 久久九九亚洲精品| 久久国产亚洲精品麻豆| 国产巨作麻豆欧美亚洲综合久久| 久久国产热精品波多野结衣AV| 久久久久无码精品国产不卡| 少妇人妻综合久久中文字幕| 欧美国产精品久久高清| 伊人 久久 精品| 精品伊人久久久| 久久中文字幕人妻熟av女|