自动搬运

查看原文

来自洛谷，原作者为

	Life AFO

搬运于2025-08-24 21:20:10，当前版本为作者最后更新于2021-06-28 19:46:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

平面上有 $n$ 个点，将其包含在 $k$ 个矩形中（不相交），求矩形的最小面积和。

$n \le 50,1\le k \le 4$

题解

我们看到 $n \le 50$，并且结合 NOIP 早期题目的数据特水的尿性，自然而然地想到深搜，所以大力深搜即可。

深搜流程：

//伪代码
void dfs(int u)
{
	if(u==n+1)
	{
		更新答案;
		return;
	}
	for(int i=0;i<k;i++)
	{
		将第u个点加入第i个矩形;
		if(矩形间不相交)
			dfs(u+1);
		将第i个矩形恢复成加入第u个点前的状态;
	}
}

不出意外，代码交上去之后跑得飞快！然后这道题就做完了！AC记录

将点加入矩形/判断矩形间是否相交较为繁琐，代码实现细节见示例代码。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,x[55],y[55],ans=0x3f3f3f3f;
struct square
{
	int empty=1,x1,x2,y1,y2;//x1<=x2 y1<=y2
	void join(int u)//将第u个点加入矩形
	{
		if(empty)
			x1=x2=x[u],y1=y2=y[u];
		empty=0;
		x1=min(x1,x[u]),x2=max(x2,x[u]);
		y1=min(y1,y[u]),y2=max(y2,y[u]);
	}
	int area(){return (x2-x1)*(y2-y1);}//计算矩形面积
}squ[4];
int is_intersect(int a,int b,int c,int d)//ab/cd四条边分属两个矩形，判断是否有其他边夹在ab/cd之间
{
	return (a<=c&&c<=b)||(a<=d&&d<=b)||(c<=a&&a<=d)||(c<=b&&b<=d);
}
int is_intersect(int num)//判断矩形之间是否相交
{
	for(int i=0;i<k;i++)
		if(num!=i&&is_intersect(squ[num].x1,squ[num].x2,squ[i].x1,squ[i].x2)&&is_intersect(squ[num].y1,squ[num].y2,squ[i].y1,squ[i].y2))
			return 1;
	return 0;
}
void dfs(int u)
{
	if(u==n+1)
	{
		int sum=0;
		for(int i=0;i<k;i++)sum+=squ[i].area();
		ans=min(ans,sum);
		return;
	}
	for(int i=0;i<k;i++)
	{
		square t=squ[i];
		squ[i].join(u);
		if(!is_intersect(i))
			dfs(u+1);
		squ[i]=t;
	}
}
int main()
{
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&x[i],&y[i]);
	dfs(1);
	printf("%d",ans);
}