• <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軸的區(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 西月弦 閱讀(751) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告經典題目
            久久AV无码精品人妻糸列| 99久久无码一区人妻| 无码八A片人妻少妇久久| 久久久国产视频| 欧洲人妻丰满av无码久久不卡| 久久99精品久久只有精品| 精品熟女少妇aⅴ免费久久| 精品综合久久久久久98| 国产精品无码久久综合| 一级a性色生活片久久无少妇一级婬片免费放 | 亚洲国产精品久久久久婷婷软件| 久久国产精品二国产精品| 久久天天躁夜夜躁狠狠躁2022| 69国产成人综合久久精品| 亚洲精品国产第一综合99久久| 久久精品欧美日韩精品| 欧美成人免费观看久久| 精品久久久久久久久久久久久久久| 欧美国产成人久久精品| 久久久久综合网久久| 色偷偷偷久久伊人大杳蕉| 怡红院日本一道日本久久 | 久久er热视频在这里精品| 亚洲精品乱码久久久久久蜜桃不卡| 久久国产精品免费一区二区三区| 亚洲午夜久久久久妓女影院| 久久中文精品无码中文字幕| 久久美女人爽女人爽| 国产午夜福利精品久久2021| 亚洲AV无码久久精品成人| 久久综合色老色| 久久中文字幕人妻熟av女| 久久人妻少妇嫩草AV蜜桃| 久久精品亚洲乱码伦伦中文| 青青国产成人久久91网| 国产91色综合久久免费分享| 久久久av波多野一区二区| 99久久99这里只有免费的精品| 国产精品一久久香蕉国产线看观看| MM131亚洲国产美女久久| 国产精品久久精品|