1. 题目

传送门＝￣ω￣＝

2. 题解

枚举每个点放进的矩形。
复杂度 5⁴⁰，所以要剪枝。

剪枝：
1. 最优性剪枝，如果当前保存的答案比当前方案的面积小，剪枝。
2. 如果有矩形相交，剪枝（这个你不剪会WA）

至于判断两矩形是否相交。。。
两矩形相交必然得到一个新矩形，判断新矩形是否合法即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef int arr[5];
int n,k,ans=INT_MAX;
pii p[55];
bool judge(arr top,arr und,arr lef,arr rig)//判断两矩形是否相交
{
    for(int i=1;i<k;i++)
        for(int j=i+1;j<=k;j++)
        {
            if(top[i]==-1000||top[j]==-1000)continue;
            int nt=min(top[i],top[j]),nu=max(und[i],und[j]),\
            nl=max(lef[i],lef[j]),nr=min(rig[i],rig[j]);
            if(nt>=nu&&nl<=nr)return 1;
        }
    return 0;
}
void dfs(int c,int tot,arr top,arr und,arr lef,arr rig)
{
    if(tot>=ans)return;
    if(judge(top,und,lef,rig))return;
    if(c>n){ans=tot;return;}
    for(int i=1;i<=k;i++)
    {
        int tb=top[i],ub=und[i],lb=lef[i],rb=rig[i],totb=tot;//copy 一遍
        top[i]=max(top[i],p[c].first),und[i]=min(und[i],p[c].first);
        lef[i]=min(lef[i],p[c].second),rig[i]=max(rig[i],p[c].second);
        if(tb!=-1000)tot+=(top[i]-und[i])*(rig[i]-lef[i])-(tb-ub)*(rb-lb);
        else tot+=(top[i]-und[i])*(rig[i]-lef[i]);
        dfs(c+1,tot,top,und,lef,rig);
        top[i]=tb,und[i]=ub,lef[i]=lb,rig[i]=rb,tot=totb;
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d%d",&p[i].first,&p[i].second);
    arr a={-1000,-1000,-1000,-1000,-1000},b={1000,1000,1000,1000,1000},\
    c={-1000,-1000,-1000,-1000,-1000},d={1000,1000,1000,1000,1000};
    //由于这里传的是指针，所以要定义四个，不能公用
    dfs(1,0,a,b,d,c),printf("%d\n",ans);
    return 0;
}