随笔-141  评论-9  文章-3  trackbacks-0
这题看了答案..

/*
ID: lorelei3
TASK: packrec
LANG: C++
*/


#include 
<fstream>
#include 
<algorithm>
#include 
<iostream>

using namespace std;

const int N = 105;

typedef 
struct Rect {
    
int width;
    
int height;
    
bool operator < (const  Rect& r)const{
        
return width<r.width || (width==r.width && height<r.height) ;
    }

}
 Rect;

Rect rotate(Rect r)
{
    Rect nr;
    nr.height 
= r.width;
    nr.width 
= r.height;
    
return nr;
}


int max(int a, int b){
    
return a>b?a:b;
}


int min(int a, int b){
    
return a<b?a:b;
}


int bestarea;
int bestheight[N];
Rect r[
4];

void record(Rect r){
    
if(r.height*r.width<bestarea || bestarea==0){
        bestarea 
= r.height*r.width;
        
for(int i=0; i<N; ++i)
            bestheight[i]
=0;
    }


    
if(r.height*r.width==bestarea){
        bestheight[min(r.height,r.width)]
=1;
    }

}


void check(){

    
int i = 0
    Rect rect;

    
//case 1
    rect.width=0;
    rect.height
=0;
    
for(i=0; i<4++i){
        rect.width 
+= r[i].width;
        rect.height 
= max(rect.height, r[i].height);
    }

    record(rect);

    
//case 2
    rect.width=0;
    rect.height
=0;
    
for(i=0; i<3;++i){
        rect.width 
+= r[i].width;
        rect.height 
= max(rect.height, r[i].height);
    }

    rect.height 
+= r[3].height;
    rect.width 
= max(rect.width, r[3].width);
    record(rect);

    
//case 3
    rect.width = r[0].width + r[1].width;
    rect.height 
= max(r[0].height, r[1].height);

    rect.width 
= max(rect.width, r[2].width);
    rect.height 
+= r[2].height;

    rect.width 
+= r[3].width;
    rect.height 
= max(rect.height, r[3].height);
    record(rect);

    
//case 4 5
    rect.width = r[0].width+r[1].width;
    rect.height 
= max(r[0].height, r[1].height);
    rect.width 
+= max(r[2].width, r[3].width);
    rect.height 
= max(rect.height , r[2].height+r[3].height);
    record(rect);

    
//case 6
    rect.height = max(r[0].height+r[2].height, r[1].height+r[3].height);
    rect.width 
= r[0].width + r[1].width;
 
    
/* do 2 and 1 touch? */
    
if(r[0].height < r[1].height)
        rect.width 
= max(rect.width, r[2].width+r[1].width);
    
/* do 2 and 3 touch? */
    
if(r[0].height+r[2].height > r[1].height)
        rect.width 
= max(rect.width, r[2].width+r[3].width);
    
/* do 0 and 3 touch? */
    
if(r[1].height < r[0].height)
        rect.width 
= max(rect.width, r[0].width+r[3].width);
 
    
/* maybe 2 or 3 sits by itself */
    rect.width 
= max(rect.width, r[2].width);
    rect.width 
= max(rect.width, r[3].width);
    record(rect);    

}



void checkrotate(int n){
    
if(n==4){
        check();
        
return;
    }

    checkrotate(n
+1);
    r[n] 
= rotate(r[n]);
    checkrotate(n
+1);
    r[n] 
= rotate(r[n]);
}


void checkpermute(){
    sort(r, r
+4);
    
do{
        checkrotate(
0);
    }
while(next_permutation(r, r+4));
}


int main(){

    
int i;
    ifstream 
in("packrec.in");
    ofstream 
out("packrec.out");

    
for(i=0; i<4++i)
        
in>>r[i].width>>r[i].height;

    checkpermute();

    
out<<bestarea<<endl;
    
for(i=0;i<N;++i){
        
if(bestheight[i]){
            
out<<i<<" "<<bestarea/i<<endl;
        }

    }


    
return 0;
}

posted on 2010-11-09 12:52 小阮 阅读(598) 评论(0)  编辑 收藏 引用 所属分类: USACO

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