P1034 矩形覆盖

· · 题解

题意

平面上有 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);
}