【正经题解】矩形覆盖

由于 $k<=4$ ，数据不大，搜索与回溯一般不会超时。将数据划分为 $k$ 部分，表示 $k$ 个矩形，用数组 $a$ 来存储两个相邻矩形的 中间点（中间点属于 前一个矩形） $a$ [ $0$ ] $=0$ , $a$ [ $k$ ] $=n$ 。
分别按 $x$ 和 $y$ 的大小进行两次排序，即代码中的两个 $sort$ （可以避免两矩形重合）。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,K,zt[55],a[10],best=0x7fffffff;
int maxn,may,mix,miy;
struct node{
    int x,y;
}w[510];
void pint(){
    int s=0;
    maxn=may=0;
    mix=miy=0x7fffffff;
    for(int i=1;i<=K;i++){
        for(int j=a[i-1]+1;j<=a[i];j++){
            maxn=max(w[j].x,maxn);
            mix=min(w[j].x,mix);
            may=max(w[j].y,may);
            miy=min(w[j].y,miy);
        }
        s+=(maxn-mix)*(may-miy);
        maxn=may=0;
        mix=miy=0x7fffffff;
    }
    if(s<best){best=s;}
}
void sousuo(int k){
    if(K==k){pint();return ;}
    for(int i=a[k-1]+1;i<=n;i++){
        if(!zt[i]){
            zt[i]=1;
            a[k]=i;
            sousuo(k+1);
            zt[i]=0;
        }
    }
}
bool cmp(node a,node b){
    if(a.x<b.x){return true;}
    if(a.x==b.x&&a.y<b.y){return true;}
    return false;
}
bool Cmp(node a,node b){
    if(a.y<b.y){return true;}
    if(a.y==b.y&&a.x<b.x){return true;}
    return false;
}
int main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        cin>>w[i].y>>w[i].x;
    }
    sort(w+1,w+n+1,cmp);
    a[K]=n;
    sousuo(1);
    sort(w+1,w+n+1,Cmp);
    sousuo(1);//两次搜索
    cout<<best;
    return 0;
}