packrec.cpp

USACO chapter one.May hope it useful to someone

/*
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;
}