• <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)  編輯 收藏 引用 所屬分類: 解題報告經典題目
            91久久精品91久久性色| 久久天天躁狠狠躁夜夜96流白浆| 精品国产乱码久久久久久郑州公司 | 草草久久久无码国产专区| 亚洲中文字幕久久精品无码APP| 久久久久综合中文字幕| 久久精品人妻中文系列| 伊人久久大香线蕉av一区| 97精品依人久久久大香线蕉97 | 996久久国产精品线观看| 久久成人影院精品777| 久久这里只有精品视频99| 日日噜噜夜夜狠狠久久丁香五月 | 91久久精一区二区三区大全| 久久人人爽人人澡人人高潮AV | 麻豆国内精品久久久久久| 亚洲AV无码久久精品成人 | 久久久不卡国产精品一区二区| 久久久久久国产a免费观看黄色大片 | 亚洲国产香蕉人人爽成AV片久久| 婷婷久久综合九色综合绿巨人| 亚洲AV无码久久精品色欲| 久久精品国产亚洲精品| 国产午夜福利精品久久2021| 久久国语露脸国产精品电影| 国产精品无码久久综合网| 久久精品国内一区二区三区| 久久精品无码专区免费青青| 国产69精品久久久久久人妻精品| 精品国产热久久久福利| 久久精品国产久精国产| 久久香蕉超碰97国产精品| 欧美日韩精品久久久久| 色8激情欧美成人久久综合电| 久久精品中文字幕一区| 久久久久国色AV免费看图片| 狠狠色综合网站久久久久久久| 99热成人精品免费久久| 91久久精品视频| 91精品久久久久久无码| 久久www免费人成精品香蕉|