|
Posted on 2010-08-10 11:57 Uriel 阅读(488) 评论(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;
}

|