题解

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n,k;
struct node{
    int x,y;
}sa[60];
struct node2{
    node l,r;
}sb[10];
int ans=INF;
bool checkit(int i,int j)
{
    if(sb[i].l.x==INF||sb[i].l.y==INF||sb[i].r.x==-INF||sb[i].r.y==-INF)  
        return 0;  
    if(sb[j].l.x==INF||sb[j].l.y==INF||sb[j].r.x==-INF||sb[j].r.y==-INF)  
        return 0;  
    if(sb[i].l.x>sb[j].r.x||sb[i].l.y>sb[j].r.y)  
       return 0;  
    if(sb[j].l.x>sb[i].r.x||sb[j].l.y>sb[i].r.y)  
       return 0;  
    return 1;  
}
bool check()
{
    for(int i=1;i<=k;i++)
    {
        for(int j=i+1;j<=k;j++)
        {
            if(checkit(i,j)) return 0;
        }
    }
    return 1;
}
int getsqr()
{
    int ans1=0;
    for(int i=1;i<=k;i++)
    {
        if(sb[i].l.x!=INF)
        {
            ans1+=(sb[i].r.x-sb[i].l.x)*(sb[i].r.y-sb[i].l.y);
        }

    }
    return ans1;
}
void dfs(int now)
{
    if(now==n+1)
    {
        ans=getsqr(); 
        return;
    }
    int x=sa[now].x,y=sa[now].y;

    for(int i=1;i<=k;i++)
    {
        node2 tmp=sb[i];
         if(sb[i].l.x>sa[now].x)  
           sb[i].l.x=sa[now].x;  
       if(sb[i].l.y>sa[now].y)  
           sb[i].l.y=sa[now].y;  
       if(sb[i].r.x<sa[now].x)  
           sb[i].r.x=sa[now].x;  
       if(sb[i].r.y<sa[now].y)  
           sb[i].r.y=sa[now].y; 
        if(check()&&getsqr()<ans)
        dfs(now+1);
        sb[i]=tmp;
    }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    cin>>sa[i].x>>sa[i].y;
    for(int i=1;i<=k;i++)
    {
        sb[i].l.x=sb[i].l.y=INF;
        sb[i].r.x=sb[i].r.y=-INF;
    }
    dfs(1);
    cout<<ans;
}