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

            USACO chapter 3 section 1 Shaping Regions

            USER: tian tianbing [tbbd4261]
            TASK: rect1
            LANG: C++

            Compiling...
            Compile: OK

            Executing...
               Test 1: TEST OK [0.000 secs, 3024 KB]
               Test 2: TEST OK [0.000 secs, 3024 KB]
               Test 3: TEST OK [0.011 secs, 3024 KB]
               Test 4: TEST OK [0.000 secs, 3024 KB]
               Test 5: TEST OK [0.000 secs, 3024 KB]
               Test 6: TEST OK [0.000 secs, 3024 KB]
               Test 7: TEST OK [0.022 secs, 3024 KB]
               Test 8: TEST OK [0.011 secs, 3024 KB]
               Test 9: TEST OK [0.022 secs, 3024 KB]
               Test 10: TEST OK [0.022 secs, 3024 KB]
               Test 11: TEST OK [0.022 secs, 3024 KB]

            All tests OK.
            Your program ('rect1') produced all correct answers!  This is your
            submission #15 for this problem.  Congratulations!
             
                 終于做出來(lái)了,用隊(duì)列實(shí)現(xiàn),沒(méi)接收一個(gè)就遍歷整個(gè)隊(duì)列。要注意的是要把隊(duì)列的大小用t記下,因?yàn)?/pre>
            
            新加進(jìn)來(lái)的會(huì)改變隊(duì)列的大小。
                用的是矩形分割:
            原來(lái)的程序在分割與a相交的矩形b的時(shí)候,把a(bǔ)與b相交的部分也作為一個(gè)小矩形放在了后面。
            這也就會(huì)多出很多,統(tǒng)計(jì)了一下對(duì)于最后一組測(cè)試數(shù)據(jù)有40多萬(wàn)個(gè)矩形,超時(shí)。
            其實(shí)應(yīng)該把a(bǔ)整個(gè)放進(jìn)去,不該把a(bǔ)也分割的。



             

            /*
            ID:tbbd4261
            PROG:rect1
            LANG:C++
            */

            #include
            <fstream>
            #include
            <queue>
            #include
            <string.h>
            using namespace std;
            ifstream fin(
            "rect1.in");
            ofstream fout(
            "rect1.out");
            struct type
            {
                   
            int x1,y1,x2,y2,color;
            };

            int w,h,n,i,cnt;
            int color[2505]={0};
            queue
            <type>Q;
            inline 
            int max(int a, int b){ return a>b?a:b; }
            inline 
            int min(int a, int b){ return a>b?b:a; } 
            bool isIn(type &a, type &b)//判斷是否相交 
            {
                
            if(a.x1>=b.x2)return false;
                
            if(a.x2<=b.x1)return false;
                
            if(a.y1>=b.y2)return false;
                
            if(a.y2<=b.y1)return false;
                
            return true;
            }

            void add(int x1, int y1, int x2, int y2, int c)
            {
                  type t; t.x1
            =x1; t.y1=y1; t.x2=x2; t.y2=y2; t.color=c; 
                  color[c]
            +=(x2-x1)*(y2-y1);
                  Q.push(t);
            }

             
            void dec()
            {
                   type t
            =Q.front(); Q.pop();
                   color[t.color]
            -=(t.x2-t.x1)*(t.y2-t.y1);
            }

             
            void deal(type &a, type &b) //a與b交,b的下標(biāo)是j                 
             {     
                 
            if(a.x1>b.x1&&a.x1<b.x2) add(b.x1, b.y1,a.x1,b.y2,b.color);//S1
                 if(a.x2>b.x1&&a.x2<b.x2) add(a.x2,b.y1, b.x2, b.y2,b.color); //S3
                 if(a.y1>b.y1&&a.y1<b.y2) add(max(a.x1,b.x1),b.y1,min(a.x2,b.x2),a.y1,b.color);//S2
                 if(a.y2>b.y1&&a.y2<b.y2) add(max(a.x1,b.x1),a.y2,min(a.x2,b.x2),b.y2,b.color);//S4
                 
            //add(max(a.x1,b.x1),max(a.y1,b.y1),min(a.x2,b.x2),min(a.y2,b.y2),a.color);//a與b相交的部分 
                 dec();
             }

            int main()
            {
                memset(color,
            0,sizeof color);
                fin
            >>w>>h>>n;
                color[
            1]=w*h;
                type temp;  
                temp.x1
            =0; temp.y1=0; temp.x2=w; temp.y2=h; temp.color=1;
                Q.push(temp);
                
            for(i=1; i<=n; i++)
                {
                         fin
            >>temp.x1>>temp.y1>>temp.x2>>temp.y2>>temp.color;
                         
            for(int t=Q.size(),j=1;j<=t; j++ )
                                 
            if(isIn(temp,Q.front() ))
                                      deal( temp,Q.front() );
                                 
            else { type t=Q.front(); Q.pop();Q.push(t); }//如果不相交,放在隊(duì)列后面
                    add(temp.x1,temp.y1,temp.x2,temp.y2,temp.color);
                }
                
            for(i=1; i<=2500; i++)
                          
            if(color[i]) fout<<i<<' '<<color[i]<<endl;  
                          
                
            return 0;
            }

             

            posted on 2010-08-04 16:51 田兵 閱讀(120) 評(píng)論(0)  編輯 收藏 引用 所屬分類: USACO

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            久久亚洲AV成人出白浆无码国产 | 久久婷婷色香五月综合激情| 国产精品内射久久久久欢欢| 久久久免费观成人影院 | 武侠古典久久婷婷狼人伊人| 久久久久人妻一区二区三区| 久久久无码一区二区三区| 国产精品免费久久| 精品久久久中文字幕人妻| 欧美777精品久久久久网| 久久伊人亚洲AV无码网站| 日日躁夜夜躁狠狠久久AV| 精品久久国产一区二区三区香蕉| yy6080久久| 亚洲精品国产成人99久久| 99久久精品免费看国产一区二区三区 | 国产69精品久久久久99尤物| 国产偷久久久精品专区| 草草久久久无码国产专区| 亚洲国产精品无码久久久蜜芽| 久久国产精品二国产精品| 国产一区二区精品久久| av色综合久久天堂av色综合在| 免费一级欧美大片久久网| 欧美亚洲另类久久综合| 精品综合久久久久久888蜜芽| 久久福利资源国产精品999| 国产亚洲精午夜久久久久久| 国内精品久久久久影院一蜜桃| 99久久国产宗和精品1上映| 色偷偷88欧美精品久久久| 一本一道久久精品综合| 狠狠综合久久综合88亚洲 | 热99re久久国超精品首页| 久久综合久久自在自线精品自 | 久久精品免费观看| 久久精品国产亚洲AV无码娇色| 性色欲网站人妻丰满中文久久不卡| 亚洲伊人久久成综合人影院| 色欲综合久久躁天天躁| 亚洲国产成人精品无码久久久久久综合|