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

            閱讀排行榜

            大美女久久久久久j久久| 久久国产精品免费| 久久精品中文字幕一区| 色综合久久中文字幕无码| 国产99久久久国产精品~~牛| 亚洲欧美日韩中文久久| 久久最新精品国产| 亚洲中文字幕无码久久2020| 99久久精品九九亚洲精品| 97久久国产露脸精品国产| 久久精品国产亚洲AV不卡| 99久久久精品免费观看国产| 国产精品日韩深夜福利久久| 久久精品人人做人人爽电影蜜月 | 99久久精品国产高清一区二区| 欧美亚洲另类久久综合婷婷 | 久久国产精品-国产精品| 久久婷婷色综合一区二区| 欧美久久精品一级c片片| 久久久噜噜噜www成人网| 久久久久久精品免费看SSS| 久久久无码精品亚洲日韩软件| 久久亚洲国产精品五月天婷| 9191精品国产免费久久| 韩国三级大全久久网站| 久久精品人人做人人妻人人玩| 久久精品国产99久久久| 国产成人综合久久精品红| 无码人妻久久一区二区三区蜜桃 | 午夜欧美精品久久久久久久| 无码人妻少妇久久中文字幕| 国产激情久久久久影院| 伊人久久综在合线亚洲2019| 中文字幕一区二区三区久久网站| 久久久精品久久久久特色影视| 亚洲欧洲精品成人久久曰影片| 亚洲七七久久精品中文国产| 亚洲va中文字幕无码久久| 欧美精品乱码99久久蜜桃| 久久久高清免费视频| 久久婷婷五月综合97色直播|