Revision: 48358
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at June 29, 2011 17:39 by Nursoltan
Initial Code
/* 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; }
Initial URL
Initial Description
Initial Title
ch1 : Packing Rectangles
Initial Tags
Initial Language
C++