USACO-Chapter1.rar_it_usaco

/* ID: chenkai4 PROG: packrec LANG: C++ */ #include<iostream> #include<fstream> using namespace std; ifstream in("packrec.in"); ofstream out("packrec.out"); int w[5],h[5];bool fuck[5]; int minanswer=10000; int sp=0,answ[1000],ansh[1000]; int max(int a,int b) {return (a>b?a:b);} int tmax(bool i1,bool i2,bool i3,bool i4) { int ttmax=0;fuck[1]=i1;fuck[2]=i2;fuck[3]=i3;fuck[4]=i4; for(int a=1;a<=4;a++) if(!fuck[a]) ttmax=max(ttmax,w[a]); return ttmax; } int tmaxh(bool i1,bool i2,bool i3,bool i4) { int ttmax=0;fuck[1]=i1;fuck[2]=i2;fuck[3]=i3;fuck[4]=i4; for(int a=1;a<=4;a++) if(!fuck[a]) ttmax=max(ttmax,h[a]); return ttmax; } int tmax2(int a,int b) { int ttmax=0; for(int c=1;c<=4;c++) if(c!=a&&c!=b) ttmax=max(ttmax,w[c]); return ttmax; } int tmax22(int a,int b) { int ttmax=0; for(int c=1;c<=4;c++) if(c!=a&&c!=b) ttmax=max(ttmax,h[c]); return ttmax; } int tadd(bool i1,bool i2,bool i3,bool i4) { int anss=0;fuck[1]=i1;fuck[2]=i2;fuck[3]=i3;fuck[4]=i4; for(int a=1;a<=4;a++) if(!fuck[a]) anss+=h[a]; return anss; } int taddw(bool i1,bool i2,bool i3,bool i4) { int anss=0;fuck[1]=i1;fuck[2]=i2;fuck[3]=i3;fuck[4]=i4; for(int a=1;a<=4;a++) if(!fuck[a]) anss+=w[a]; return anss; } int tadd2h(int a,int b) { int anss=0; for(int c=1;c<=4;c++) if(c!=a&&c!=b) anss+=h[c]; return anss; } int tadd2w(int a,int b) { int anss=0; for(int c=1;c<=4;c++) if(c!=a&&c!=b) anss+=w[c]; return anss; } int main() { for(int a=1;a<=4;a++) in>>w[a]>>h[a]; int t; //----------------------------------State 1------------------------------------------- for(int a=1;a<=2;a++) { t=w[1];w[1]=h[1];h[1]=t; for(int b=1;b<=2;b++) { t=w[2];w[2]=h[2];h[2]=t; for(int c=1;c<=2;c++) { t=w[3];w[3]=h[3];h[3]=t; for(int d=1;d<=2;d++) { t=w[4];w[4]=h[4];h[4]=t; int width = (w[1]+w[2]+w[3]+w[4]); int height = max(h[1],max(h[2],max(h[3],h[4]))); if(width*height<minanswer) {sp=0;answ[++sp]=width;ansh[sp]=height;minanswer=width*height;} else if(width*height==minanswer) {answ[++sp]=width;ansh[sp]=height;minanswer=width*height;} } } } } //------------------------------------------------------------------------------------ //----------------------------------State 2------------------------------------------- for(int a=1;a<=4;a++) { for(int b=1;b<=2;b++) { t=w[1];w[1]=h[1];h[1]=t; for(int c=1;c<=2;c++) { t=w[2];w[2]=h[2];h[2]=t; for(int d=1;d<=2;d++) { t=w[3];w[3]=h[3];h[3]=t; for(int e=1;e<=2;e++) { t=w[4];w[4]=h[4];h[4]=t; int height = tmaxh(a==1,a==2,a==3,a==4) + h[a]; int width = max(w[a],taddw(a==1,a==2,a==3,a==4)); if(width*height<minanswer) {sp=0;answ[++sp]=width;ansh[sp]=height;minanswer=width*height;} else if(width*height==minanswer) {answ[++sp]=width;ansh[sp]=height;minanswer=width*height;} } } } } } //------------------------------------------------------------------------------------ //----------------------------------State 3------------------------------------------- for(int a=1;a<=4;a++) { for(int b=1;b<=4;b++) { if(a!=b) { for(int c=1;c<=2;c++) { t=w[1];w[1]=h[1];h[1]=t; for(int d=1;d<=2;d++) { t=w[2];w[2]=h[2];h[2]=t; for(int e=1;e<=2;e++) { t=w[3];w[3]=h[3];h[3]=t; for(int f=1;f<=2;f++) { t=w[4];w[4]=h[4];h[4]=t; int height = max(h[b],tmax22(a,b)+h[a]); int width = max(w[a],tadd2w(a,b))+w[b]; if(height*width<minanswer) {sp=0;answ[++sp]=width;ansh[sp]=height;minanswer=width*height;} else if(height*width==minanswer) {answ[++sp]=width;ansh[sp]=height;} } } } } } } } //------------------------------------------------------------------------------------ //----------------------------------State 4&5----------------------------------------- for(int a=1;a<=4;a++) { for(int b=1;b<=4;b++) { if(a!=b) { for(int c=1;c<=2;c++) { t=w[1];w[1]=h[1];h[1]=t; for(int d=1;d<=2;d++) { t=w[2];w[2]=h[2];h[2]=t; for(int e=1;e<=2;e++) { t=w[3];w[3]=h[3];h[3]=t; for(int f=1;f<=2;f++) { t=w[4];w[4]=h[4];h[4]=t; int height = max(h[a],max(h[b],tadd2h(a,b))); int width = w[a]+tmax2(a,b)+w[b]; if(height*width<minanswer) {sp=0;answ[++sp]=width;ansh[sp]=height;minanswer=width*height;} else if(height*width==minanswer) {answ[++sp]=width;ansh[sp]=height;} } } } } } } } //------------------------------------------------------------------------------------ //----------------------------------State 6------------------------------------------- for(int a=1;a<=4;a++) { for(int b=1;b<=4;b++) { if(a!=b) { for(int c=1;c<=4;c++) { if(a!=c&&b!=c) { for(int d=1;d<=4;d++) { if(a!=d&&b!=d&&c!=d) { for(int e=1;e<=2;e++) { t=w[1];w[1]=h[1];h[1]=t; for(int f=1;f<=2;f++) { t=w[2];w[2]=h[2];h[2]=t; for(int g=1;g<=2;g++) { t=w[3];w[3]=h[3];h[3]=t; for(int i=1;i<=2;i++) { t=w[4];w[4]=h[4];h[4]=t; int height = max(h[a]+h[b],h[c]+h[d]); if(w[d]>=w[c]&&h[c]<h[a]) continue; if(w[b]>=w[a]&&h[a]<h[c]) continue; int width = max(w[a]+w[c],w[b]+w[d]); if(height*width<minanswer) {sp=0;answ[++sp]=width;ansh[sp]=height;minanswer=width*height;} else if(height*width==minanswer) {answ[++sp]=width;ansh[sp]=height;} } } } } } } } } } } } //------------------------------------------------------------------------------------ for(int a=1;a<=sp;a++) { if(answ[a]>ansh[a]) {t=answ[a];answ[a]=ansh[a];ansh[a]=t;} for(int b=a-1;b>=1;b--) { if(answ[b]==answ[a]) { for(int c=a;c<sp;c++) {answ[c]=answ[c+1];ansh[c]=ansh[c+1];} sp--; a--; break; } } } for(int a=1;a<sp;a++) for(int b=a+1;b<=sp;b++) { if(answ[b]<answ[a]) {t=answ[b];answ[b]=answ[a];answ[a]=t; t=ansh[b];ansh[b]=ansh[a];ansh[a]=t;} } out<<minanswer<<endl; for(int a=1;a<=sp;a++) out<<answ[a]<<" "<<ansh[a]<<endl; return 0; }