Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1169 Packing Rectangles---模拟

Posted on 2010-08-10 11:57 Uriel 阅读(480) 评论(0)  编辑 收藏 引用 所属分类: POJ模拟
        比较麻烦的模拟,倒不是方法难,主要情况多,过程很简单,就是题目给的那几种情况枚举(开始以为随便放置,所以一直以为是大自然题,所以放了一年没做。。),题目的case 4 & case 5 可以合并~

        每种case都要考虑横放和竖放两种情况,最后一种case还要考虑四个矩形的相对位置。。写了一晚上+一早上。。代码很挫。。


#include<stdio.h>
#include
<stdlib.h>
#include
<algorithm>
using namespace std;

#define INF 0x7fffffff

struct Ans{
    
int w,h,area;
}
res[3000];

bool cmp(Ans a,Ans b){
    
if(a.area!=b.area)return a.area<b.area;
    
else
        
return a.w<b.w;
}


int dir[24][4]={{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,2,1},{0,3,1,2},
                
{1,2,3,0},{1,2,0,3},{1,0,2,3},{1,0,3,2},{1,3,2,0},{1,3,0,2},
                
{2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},{2,3,1,0},{2,3,0,1},
                
{3,0,1,2},{3,0,2,1},{3,1,0,2},{3,1,2,0},{3,2,1,0},{3,2,0,1}}
;
int W,H,n;
int w[5],h[5];

int main(){
    
int i,j,k,tmp,cf;
    
int tw[5],th[5];//case 5 中暂存每个矩形长宽
    int flagw,flagh,flaghh,flagww; //暂存特殊矩形的长宽
    int flag[5]; //case 5 中每个矩形横放/竖放的情况
    for(i=0;i<4;i++)scanf("%d %d",&w[i],&h[i]);
    n
=0//num of res

    
//-----------------------------------case 1
    
//0->横放 1->(旋转180)竖放
    for(i=0;i<16;i++){
        tmp
=i; cf=4;
        H
=0; W=0;
        
while(cf--){
            
if(tmp&1){
                W
+=h[cf]; H=max(w[cf],H);
            }

            
else{
                W
+=w[cf]; H=max(h[cf],H);
            }

            tmp
/=2;
        }
    
//        printf("W=%d H=%d\n",W,H);
        if(W>H)swap(W,H);
        res[n].area
=W*H;
        res[n].w
=W;
        res[n
++].h=H;
    }


    
//-----------------------------------case 2
    
//0->横放 1->(旋转180)竖放
    for(i=0;i<4;i++){
        
for(j=0;j<16;j++){
            tmp
=j;cf=4;
            H
=0;W=0;
            
while(cf--){
                
if(cf==i){
                    
if(tmp&1){
                        flagw
=h[cf]; flagh=w[cf];
                    }

                    
else{
                        flagw
=w[cf]; flagh=h[cf];
                    }

                }

                
else{
                    
if(tmp&1){
                        H
=max(H,w[cf]); W+=h[cf];
                    }

                    
else{
                        H
=max(H,h[cf]); W+=w[cf];
                    }

                }

                tmp
/=2;
            }

            H
+=flagh;
            W
=max(W,flagw);
//            printf("W=%d H=%d\n",W,H);
            if(W>H)swap(W,H);
            res[n].area
=W*H;
            res[n].w
=W;
            res[n
++].h=H;
        }

    }


    
//-----------------------------------case 3--------------------WA
    
//0->横放 1->(旋转180)竖放
    for(i=0;i<4;i++){
        
for(j=0;j<4;j++){
            
if(i==j)continue;
            
for(k=0;k<16;k++){
                tmp
=k;cf=4;
                W
=0;H=0;
                
while(cf--){
                    
if(cf==i){
                        
if(tmp & 1){
                            flaghh
=w[i]; flagww=h[i];
                        }

                        
else{
                            flaghh
=h[i]; flagww=w[i];
                        }

                    }

                    
else if(cf==j){
                        
if(tmp & 1){
                            flagh
=w[j]; flagw=h[j];
                        }

                        
else{
                            flagh
=h[j]; flagw=w[j];
                        }

                    }

                    
else{
                        
if(tmp & 1){
                            W
+=h[cf]; H=max(H,w[cf]);
                        }

                        
else{
                            W
+=w[cf]; H=max(H,h[cf]);
                        }

                    }

                    tmp
/=2;
                }

                H
=max(flaghh,H+flagh);
                W
=max(W,flagw)+flagww;
//                printf("W=%d H=%d\n",W,H);
                if(W>H)swap(W,H);
                res[n].area
=W*H;
                res[n].w
=W;
                res[n
++].h=H;
            }

        }

    }


    
//-----------------------------------case 4
    
//0->横放 1->(旋转180)竖放
    for(i=0;i<4;i++){
        
for(j=0;j<4;j++){
            
if(i==j)continue;
            
for(k=0;k<16;k++){
                tmp
=k;cf=4;
                W
=0;H=0;
                
while(cf--){
//                    printf("cf=%d\n",cf);
                    if(cf==i){
                        
if(tmp & 1){
                            flaghh
=w[i]; flagww=h[i];
                        }

                        
else{
                            flaghh
=h[i]; flagww=w[i];
                        }

                    }

                    
else if(cf==j){
                        
if(tmp & 1){
                            flagh
=w[j]; flagw=h[j];
                        }

                        
else{
                            flagh
=h[j]; flagw=w[j];
                        }

                    }

                    
else{
                        
if(tmp & 1){
                            W
+=h[cf]; H=max(H,w[cf]);
                        }

                        
else{
                            W
+=w[cf]; H=max(H,h[cf]);
                        }

//                        printf("W=%d H=%d\n",W,H);
                    }

                    tmp
/=2;
                }

                H
=max(flaghh+flagh,H);
                W
=max(flagw,flagww)+W;
//                printf("W=%d H=%d\n",W,H);
                if(W>H)swap(W,H);
                res[n].area
=W*H;
                res[n].w
=W;
                res[n
++].h=H;
            }

        }

    }


    
//-----------------------------------case 5
    
//0->横放 1->(旋转180)竖放            
    for(i=0;i<16;i++){
        
for(k=0;k<24;k++){
            W
=0;H=0;
            tmp
=i;cf=4;
            
for(j=0;j<4;j++){
                flag[j]
=i&(1<<(j));
                
if(flag[j]){
                    tw[dir[k][j]]
=h[j];
                    th[dir[k][j]]
=w[j];
                }

                
else{
                    tw[dir[k][j]]
=w[j];
                    th[dir[k][j]]
=h[j];
                }

            }

            
if(th[2]>=th[1]+th[3]){
                H
=th[0]+th[2];
                W
=max(max(tw[0],tw[1]+tw[2]),tw[3]+tw[2]);
            }

            
else if(th[2]>th[3&& th[2]<th[1]+th[3]){
                H
=max(th[0]+th[2],th[1]+th[3]);
                W
=max(max(tw[0]+tw[1],tw[1]+tw[2]),tw[2]+tw[3]);
            }

            
else if(th[3]>th[2&& th[3]<th[0]+th[2]){
                W
=max(max(tw[0]+tw[1],tw[0]+tw[3]),tw[2]+tw[3]);
                H
=max(th[0]+th[2],th[1]+th[3]);
            }

            
else if(th[3]>=th[0]+th[2]){
                H
=th[1]+th[3];
                W
=max(max(tw[1],tw[0]+tw[3]),tw[2]+tw[3]);
            }

            
else if(th[2]==th[3]){
                H
=max(th[0]+th[2],th[1]+th[3]);
                W
=max(tw[0]+tw[1],tw[2]+tw[3]);
            }

    
//        printf("W=%d H=%d\n",W,H);
            if(W>H)swap(W,H);
            res[n].area
=W*H;
            res[n].w
=W;
            res[n
++].h=H;
        }

    }

    sort(res,res
+n,cmp);
    printf(
"%d\n",res[0].area);
    printf(
"%d %d\n",res[0].w,res[0].h);
    
int pre=0;
//    printf("\n\n");
    for(i=0;i<n;i++){
        
if(res[i].area==res[0].area && res[i].w!=res[pre].w){
            pre
=i;
            printf(
"%d %d\n",res[i].w,res[i].h);
        }

//        printf("%d %d %d\n",res[i].area,res[i].w,res[i].h);
    }

    
return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理