/ Published in: C++
                    
                                        
                            
                                Expand |
                                Embed | Plain Text
                            
                        
                        Copy this code and paste it in your HTML
/*
NAME : Nursoltan
PROB : packrec
LANG : C++
DATE : 29/06/11 15:14
*/
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <sstream>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <utility>
#include <queue>
using namespace std;
#define MAX 100
#define INF INT_MAX
#define eps (1e-9)
#define FOR(_i,_k,_n) for(int (_i)=(_k); (_i)<(_n); (_i)++)
#define FORR(_i,_k,_n) for(int (_i)=(_k); (_i)>=(_n); (_i)--)
#define CLR(_x) memset((_x),0,sizeof(_x))
#define SQR(_x) ((_x)*(_x))
#define all(_x) _x.begin(),_x.end()
#define sz(_x) sizeof(_x)
#define vc vector<int>
#define pb push_back
#define mp make_pair
#define iss istringstream
#define oss ostringstream
#define h first
#define l second
typedef long long ll;
typedef pair <int,int> rect;
int ABS(int _x){ return _x>0?_x:-_x; }
rect r,f;
vector<rect> ans;
int max3(int a, int b, int c){
return max(a,max(b,c));
}
int max4(int a, int b, int c, int d){
return max(max3(a,b,c),d);
}
int layer1(rect a, rect b, rect c, rect d){
int l,h;
h=max4(a.h,b.h,c.h,d.h);
l=a.l+b.l+c.l+d.l;
r=mp(h,l);
return h*l;
}
int layer2(rect a, rect b, rect c, rect d){
int l,h;
h=max3(a.h,b.h,c.h)+d.h;
l=max(a.l+b.l+c.l,d.l);
r=mp(h,l);
return h*l;
}
int layer3(rect a, rect b, rect c, rect d){
int l,h;
h=max3(d.h,a.h+c.h,b.h+c.h);
l=d.l+max(c.l,a.l+b.l);
r=mp(h,l);
return h*l;
}
int layer4(rect a, rect b, rect c, rect d){
int l,h;
h=max3(a.h,c.h,b.h+d.h);
l=a.l+c.l+max(b.l,d.l);
r=mp(h,l);
return h*l;
}
int layer5(rect a, rect b, rect c, rect d){
int l,h;
h=max3(b.h,c.h,a.h+d.h);
l=max(a.l,d.l)+b.l+c.l;
r=mp(h,l);
return h*l;
}
int layer6(rect a, rect b, rect c, rect d){
int l,h;
h=max(a.h+b.h,c.h+d.h);
l=max(a.l,b.l)+max(c.l,d.l);
if(c.l>d.l && a.l<b.l && b.h<d.h) l-=min(c.l-d.l,b.l-a.l);
r=mp(h,l);
return h*l;
}
int getMin(int a, int b){
if(b<a){ f=r; }
ans.pb(r);
return min(a,b);
}
int main(){
freopen("packrec.in","r",stdin);
freopen("packrec.out","w",stdout);
rect a[4];
FOR(i,0,4) cin>>a[i].h>>a[i].l;
int ret=100000;
int ord[4]={0,1,2,3};
do{
FOR(bit,0,(1<<4)){
rect b[4]={a[0],a[1],a[2],a[3]};
FOR(i,0,4) if(bit & (1<<i)) swap(b[i].h,b[i].l);
ret=getMin(ret,layer1(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
ret=getMin(ret,layer2(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
ret=getMin(ret,layer3(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
ret=getMin(ret,layer4(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
ret=getMin(ret,layer6(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
}
}while(next_permutation(ord,ord+4));
vector<rect> realAns;
FOR(i,0,ans.size()) if(ans[i].l*ans[i].h==ret){
if(ans[i].l<ans[i].h) swap(ans[i].l,ans[i].h);
realAns.pb(ans[i]);
}
sort(all(realAns));
cout<<ret<<endl;
cout<<realAns[0].h<<" "<<realAns[0].l<<endl;
FOR(i,1,realAns.size()){
if(realAns[i].h==realAns[i-1].h &&
realAns[i].l==realAns[i-1].l) continue;
cout<<realAns[i].h<<" "<<realAns[i].l<<endl;
}
//system("pause");
return 0;
}
Comments
 Subscribe to comments
                    Subscribe to comments
                
                