|
|
Posted on 2010-08-10 11:57 Uriel 閱讀(508) 評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi): POJ 、 模擬
比較麻煩的模擬，倒不是方法難，主要情況多，過(guò)程很簡(jiǎn)單，就是題目給的那幾種情況枚舉(開(kāi)始以為隨便放置，所以一直以為是大自然題，所以放了一年沒(méi)做。。)，題目的case 4 & case 5 可以合并~ 每種case都要考慮橫放和豎放兩種情況，最后一種case還要考慮四個(gè)矩形的相對(duì)位置。。寫(xiě)了一晚上+一早上。。代碼很挫。。
 #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 中暫存每個(gè)矩形長(zhǎng)寬
int flagw,flagh,flaghh,flagww; //暫存特殊矩形的長(zhǎng)寬
int flag[5]; //case 5 中每個(gè)矩形橫放/豎放的情況
for(i=0;i<4;i++)scanf("%d %d",&w[i],&h[i]);
n=0; //num of res
//-----------------------------------case 1
//0->橫放 1->(旋轉(zhuǎn)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->(旋轉(zhuǎn)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->(旋轉(zhuǎn)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->(旋轉(zhuǎn)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->(旋轉(zhuǎn)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;
}
|