• <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>

            pku 1188 Gleaming the Cubes 矩形切割

            題意是說給出n個正方體,要求求出重疊n次的子長方體體積。
            這題開始理解錯題意了,以為要求重疊的體積,懶得寫線段樹,就直接矩形切割,最壞復雜度n4,這題數(shù)據(jù)也水的可以,竟然讓我過了,后來想了下,正確的做法應該是枚舉長方體的端點,求左下角的點和右上角的點,然后直接算體積。。。
            貼個水過去的代碼吧。。
             1 # include <cstdio>
             2 using namespace std;
             3 # include <vector>
             4 # include <map>
             5 # include <algorithm>
             6 # include <iostream>
             7 struct node
             8 {
             9    int x1,x2,y1,y2,z1,z2;
            10    bool operator<(const node &pos) const
            11    {
            12         if(x1!=pos.x1) return x1<pos.x1;
            13         else if(x2!=pos.x2) return x2<pos.x2;
            14         else if(y1!=pos.y1) return y1<pos.y1;
            15         else if(y2!=pos.y2) return y2<pos.y2;
            16         else if(z1!=pos.z1) return z1<pos.z1;
            17         else return z2<pos.z2;
            18    }
            19    node(int x1,int y1,int z1,int x2,int y2,int z2)
            20    {
            21       this->x1=x1;
            22       this->y1=y1;
            23       this->x2=x2;
            24       this->y2=y2;
            25       this->z1=z1;
            26       this->z2=z2;
            27    }
            28 };
            29 map<node,int> refer;
            30 vector<int> x;
            31 vector<int> y;
            32 vector<int> z;
            33 vector<node> data;
            34 int main()
            35 {
            36 
            37   
            38     while(true)
            39     {
            40        int num,total=0;
            41        refer.clear();
            42        x.clear();
            43        y.clear();
            44        z.clear();
            45        data.clear();
            46        scanf("%d",&num);
            47        if(!num) break;
            48        while(num--)
            49        {
            50           int tx,ty,tz,len;
            51           scanf("%d%d%d%d",&tx,&ty,&tz,&len);
            52           data.push_back(node(tx,ty,tz,tx+len,ty+len,tz+len));
            53           x.push_back(tx);x.push_back(tx+len);
            54           y.push_back(ty);y.push_back(ty+len);
            55           z.push_back(tz);z.push_back(tz+len);
            56        }
            57        sort(x.begin(),x.end());
            58        vector<int>::iterator end=unique(x.begin(),x.end());
            59        while(x.end()!=end)
            60           x.pop_back();
            61        sort(y.begin(),y.end());
            62        end=unique(y.begin(),y.end());
            63        while(y.end()!=end)
            64           y.pop_back();
            65        sort(z.begin(),z.end());
            66        end=unique(z.begin(),z.end());
            67        while(z.end()!=end)
            68           z.pop_back();
            69        for(int i=0;i<data.size();i++)
            70        {
            71           vector<int>::iterator zbegin=lower_bound(z.begin(),z.end(),data[i].z1),zend=lower_bound(z.begin(),z.end(),data[i].z2),
            72                                 ybegin=lower_bound(y.begin(),y.end(),data[i].y1),yend=lower_bound(y.begin(),y.end(),data[i].y2),
            73                                 xbegin=lower_bound(x.begin(),x.end(),data[i].x1),xend=lower_bound(x.begin(),x.end(),data[i].x2);
            74           for(vector<int>::iterator zp=zbegin;zp!=zend;zp++)
            75                for(vector<int>::iterator yp=ybegin;yp!=yend;yp++)
            76                    for(vector<int>::iterator xp=xbegin;xp!=xend;xp++)
            77                    {
            78                       node tmp(*xp,*yp,*zp,*(xp+1),*(yp+1),*(zp+1));
            79                       //printf("%d %d %d %d %d %d\n",tmp.x1,tmp.y1,tmp.z1,tmp.x2,tmp.y2,tmp.z2);
            80                       
            81                       refer[tmp]++;
            82                       if(refer[tmp]==data.size())
            83                          total+=(tmp.x2-tmp.x1)*(tmp.y2-tmp.y1)*(tmp.z2-tmp.z1);
            84                    
            85                    }
            86                        
            87        }
            88        printf("%d\n",total);
            89     }
            90     return 0;
            91 }
            92 


            posted on 2010-11-06 23:19 yzhw 閱讀(150) 評論(0)  編輯 收藏 引用 所屬分類: data struct

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統(tǒng)計

            公告

            統(tǒng)計系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国产精品无码久久综合网| 国产亚洲精久久久久久无码77777| 亚洲AV无码久久精品成人| 久久99热这里只有精品国产| 亚洲国产精品久久久天堂| 久久青青草原精品影院| 无码人妻久久一区二区三区蜜桃| 超级碰碰碰碰97久久久久| 久久精品国产亚洲AV电影| 久久99国产精品久久99| 久久精品国产精品亚洲艾草网美妙| 久久婷婷五月综合成人D啪 | 国产亚洲精久久久久久无码AV| 久久国产影院| 国产91色综合久久免费分享| 亚洲国产成人久久精品99| 久久最近最新中文字幕大全| 一本色道久久综合亚洲精品| 久久国产精品免费一区二区三区| 亚洲综合熟女久久久30p| 亚洲欧美国产精品专区久久| 麻豆精品久久精品色综合| 久久久久AV综合网成人| 久久天天躁狠狠躁夜夜avapp| 国产精品伊人久久伊人电影| 99re久久精品国产首页2020| 婷婷五月深深久久精品| 一本一道久久a久久精品综合 | 99久久精品国产麻豆| 亚洲欧美日韩中文久久| 女同久久| 中文字幕无码久久人妻| 一本综合久久国产二区| 亚洲伊人久久成综合人影院 | 99久久精品九九亚洲精品| 99久久无色码中文字幕| 91精品国产高清久久久久久io | 国产精品一久久香蕉国产线看观看| 日本WV一本一道久久香蕉| 精品久久久久久久国产潘金莲 | 久久婷婷五月综合色奶水99啪|