2818032_ac_0ms_80k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 109 行

#include <stdio.h>
#include <algorithm>

using namespace std;

struct node
{
	int sum;
	int b[2];
};

int n, res, len, wid;
node rec[4], ans[100];

bool cmp(node a,node b)
{
	return a.b[0] < b.b[0];
}

int max(int a,int b)
{
	return a < b ? b : a;
}

int min(int a,int b)
{
	return a > b ? b : a;
}

void save()
{
	if(len * wid < res)
	{
		n = 0;
		res = len * wid;
		ans[n].b[0] = min(len,wid);
		ans[n].b[1] = max(len,wid);
		n++;
	}
	else
		if(len * wid == res)
		{
			ans[n].b[0] = min(len,wid);
			ans[n].b[1] = max(len,wid);
			n++;
		}
}

int main()
{
	int array[] = {0,1,2,3};
	int a, b, c, d, i, j;
	int len1, len2, len3, len4;
	int wid1, wid2 ,wid3, wid4;

	res = 2100000000;
	n = 0;
	for(i = 0; i < 4; i++)
		scanf("%d%d",&rec[i].b[0],&rec[i].b[1]),rec[i].sum = rec[i].b[0]+rec[i].b[1];
	do
	{
		for(a = 0; a < 2; a++)
		{
			len1 = rec[array[0]].b[a];
			wid1 = rec[array[0]].sum - len1;
			for(b = 0; b < 2; b++)
			{
				len2 = rec[array[1]].b[b];
				wid2 = rec[array[1]].sum - len2;
				for(c = 0; c < 2; c++)
				{
					len3 = rec[array[2]].b[c];
					wid3 = rec[array[2]].sum - len3;
					for(d = 0; d < 2; d++)
					{
						len4 = rec[array[3]].b[d];
						wid4 = rec[array[3]].sum - len4;
						len = len1+len2+len3+len4;
						wid = max(max(wid1,wid2),max(wid3,wid4));
						save();
						len = max(len1+len2+len3,len4);
						wid = max(wid1,max(wid2,wid3))+wid4;
						save();
						len = len1+max(len2+len3,len4);
						wid = max(wid1,max(wid2,wid3)+wid4);
						save();
						len = len1+len2+max(len3,len4);
						wid = max(max(wid1,wid2),wid3+wid4);
						save();
						len = max(len1+len4,max(len2+len3,len1+len3));
						wid = max(wid1+wid2,max(wid3+wid4,wid2+wid4));
						save();
					}
				}
			}
		}
	}while(next_permutation(array,array+4));
	sort(ans,ans+n,cmp);
	printf("%d\n",res);
	for(i = 0; i < n; i++)
	{
		printf("%d %d\n",ans[i].b[0],ans[i].b[1]);
		j = i;
		while(j<n&&ans[j].b[0]==ans[i].b[0])
			j++;
		i = j-1;
	}
	return 0;
}