自动搬运

查看原文

来自洛谷，原作者为

	七喜 **

搬运于2025-08-24 21:22:29，当前版本为作者最后更新于2018-10-25 21:56:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，这是一道很简单很麻烦的模拟题，具体摆放方式题目已经给出了，于是就根据题目来写就好了;

其次，看见前面的dalao使用for循环找排列，我用了dfs的方式(苣蒻标配);

放代码(代码里标了一些容易出错的地方以及解释，大概能看懂吧...)

#include<bits/stdc++.h>
using namespace std;

int x[5],y[5],ans=10000,tot,tmpx[5],tmpy[5];
bool vis[5],c[1005];

void alter(int x,int y)
{
	if(x*y<ans)//更新值
	{
		ans=x*y;
		memset(c,0,sizeof(c));
	}
	if(x*y==ans) c[x]=c[y]=1;
}

void check()//x表示宽//就是横着的线，y表示高//就是竖着的线咯;
{
	int x,y;
	/*
		编号顺序：
		1 2 3 4
		1 2 3 4
	*/
	x=tmpx[1]+tmpx[2]+tmpx[3]+tmpx[4];
	y=max(max(tmpy[1],tmpy[2]),max(tmpy[3],tmpy[4]));
	alter(x,y);
	/*
		编号顺序：
		1 2 3
		4 4 4
	*/
	x=max(tmpx[1]+tmpx[2]+tmpx[3],tmpx[4]);
	y=max(tmpy[1],max(tmpy[2],tmpy[3]))+tmpy[4];
	alter(x,y);
	/*
		编号顺序：
		1 2 4
		3 3 4
	*/
	x=max(tmpx[1]+tmpx[2],tmpx[3])+tmpx[4];
	y=max(max(tmpy[1],tmpy[2])+tmpy[3],tmpy[4]);
	alter(x,y);
	/*
		编号顺序：//然后发现4,5种情况没有什么实质性的差别，于是合并它们;
		1 2 4
		1 3 4
	*/
	x=tmpx[1]+max(tmpx[2],tmpx[3])+tmpx[4];
	y=max(tmpy[1],max(tmpy[2]+tmpy[3],tmpy[4]));
	alter(x,y);
	/*将矩形按照如下编号：
		1 2
		3 4
	  然后?...然后自己画图分析吧
	*/
	y=max(tmpy[1]+tmpy[3],tmpy[2]+tmpy[4]);
	if(tmpy[1]+tmpy[3]<=tmpy[4])	x=max(tmpx[2],max(tmpx[1],tmpx[3])+tmpx[4]);
	else if(tmpy[3]<=tmpy[4]&&tmpy[1]+tmpy[3]>=tmpy[4]) x=max(tmpx[1]+tmpx[2],max(tmpx[1],tmpx[3])+tmpx[4]);
		 else if(tmpy[3]>=tmpy[4]&&tmpy[3]<=tmpy[2]+tmpy[4]) x=max(tmpx[1]+tmpx[2],max(tmpx[2],tmpx[4])+tmpx[3]);
			  else if(tmpy[3]>=tmpy[2]+tmpy[4]) x=max(tmpx[1],max(tmpx[2],tmpx[4])+tmpx[3]);
	alter(x,y);//恩，注意考虑等于号的临界状态;
}

void dfs(int yj)//dfs生成排列
{
	if(yj==4)
	{
		check();return ;
	}
	for(int i=1;i<5;i++)
		if(!vis[i])
		{
			tmpx[yj+1]=x[i],tmpy[yj+1]=y[i],vis[i]=1;
			dfs(yj+1);
			tmpx[yj+1]=y[i],tmpy[yj+1]=x[i];
			dfs(yj+1);
			vis[i]=tmpx[yj+1]=tmpy[yj+1]=0;
		}
}

int main(){
	for(int i=1;i<5;i++) scanf("%d%d",&x[i],&y[i]);
	dfs(0);
	printf("%d\n",ans);
	for(int i=1;i<=sqrt(ans);i++)
		if(c[i]) printf("%d %d\n",i,ans/i);
	return 0;
}

附：编号排序是我对矩形编的号，有助于代码理解;