记录编号	590299	评测结果	AAAAAAA
题目名称	[NOIP 2002]矩形覆盖	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.561 s
提交时间	2024-07-09 21:43:48	内存使用	1.64 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 5e5+10,inf = 1e8;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}


int n,k;
struct made{
    int x = inf,y = inf,xx = -inf,yy = -inf;
}b[10];
struct node{
    int x,y;
}a[60];

ll ans = inf;
ll sum(){
	ll s = 0;
	for(int i = 1;i <= 4;i++)
        if(b[i].x != inf)s += (b[i].xx - b[i].x) * (b[i].yy - b[i].y);
    return s;
}
void dfs(int x){
	if(sum() > ans)return; 
    if(x == n+1){
        for(int i = 1;i <= 4;i++)
            for(int j = i+1;j <= 4;j++)
                if(b[i].x <= b[j].xx && b[i].xx >= b[j].x && b[i].y <= b[j].yy && b[i].yy >= b[j].y)return;
        ll s = 0;
        for(int i = 1;i <= 4;i++)
            if(b[i].x != inf)s += (b[i].xx - b[i].x) * (b[i].yy - b[i].y);
        ans = min(ans,s);
        return;
    }
    made now;
    for(int i = 1;i <= k;i++){
        now = b[i];
        b[i].x = min(b[i].x,a[x].x),b[i].xx = max(b[i].xx,a[x].x);
        b[i].y = min(b[i].y,a[x].y),b[i].yy = max(b[i].yy,a[x].y);
        dfs(x+1);
        b[i] = now;
    }
}
int main(){
    freopen("jxfg.in","r",stdin);
    freopen("jxfg.out","w",stdout);
    n = read(),k = read();
    for(int i = 1;i <= n;i++)a[i].x = read(),a[i].y = read();
    dfs(1);
    printf("%lld\n",ans);
    
    return cerr<<clock()<<"ms"<<endl,0;
    
}