记录编号	575819	评测结果	AAAAAAA
题目名称	[NOIP 2002]矩形覆盖	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.060 s
提交时间	2022-09-28 20:08:39	内存使用	0.82 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, xi[110], yi[110], ans;
struct node {
	int xl, yl, xr, yr, use, s;
}jx[10];
bool check(int x) {
	for(int i = 1; i <= m; i ++) {
		if(!jx[i].use || i == x) {
			continue;
		}
		if(((jx[x].xl <= jx[i].xr && jx[x].xl >= jx[i].xl) || (jx[x].xr <= jx[i].xr && jx[x].xr >= jx[i].xl)) && ((jx[x].yl <= jx[i].yr && jx[x].yl >= jx[i].yl) || (jx[x].yr <= jx[i].yr && jx[x].yr >= jx[i].yl))) {
			return true;
		}
	}
	return false;
}
void add(int x, int k) {
	if(!jx[k].use) {
//		cout << x << endl;
		jx[k].use = 1;
		jx[k].xl = xi[x];
		jx[k].xr = xi[x];
		jx[k].yl = yi[x];
		jx[k].yr = yi[x];
		return ;
	}
//	cout << ' ' << x << endl;
	jx[k].xl = min(jx[k].xl, xi[x]);
	jx[k].xr = max(jx[k].xr, xi[x]);
	jx[k].yl = min(jx[k].yl, yi[x]);
	jx[k].yr = max(jx[k].yr, yi[x]);
	jx[k].s = (jx[k].xr - jx[k].xl) * (jx[k].yr - jx[k].yl);
}
void dfs(int x, int cs, int sum) {
//	cout << x - 1 << ' ' << cs << ' ' << sum << endl; 
	for(int i = 1; i <= cs; i ++) {
//		cout << jx[i].xl << ' ' << jx[i].xr << ' ' << jx[i].yl << ' ' << jx[i].yr << ' ' << jx[i].s << endl;
	}
	if(sum >= ans || x > n + 1) {
		return ;
	}
	if(x == n + 1) {
		ans = min(ans, sum);
		return ;
	}
	if(cs < m) {
		add(x, cs + 1);
		if(!check(cs + 1)) {
			dfs(x + 1, cs + 1, sum);
		}
		jx[cs + 1].use = 0;
	}
	for(int i = 1; i <= cs; i ++) {
		int xl = jx[i].xl, xr = jx[i].xr, yl = jx[i].yl, yr = jx[i].yr, s = jx[i].s;
		add(x, i);
		if(!check(i)) {
			dfs(x + 1, cs, sum + jx[i].s - s);
		}
		jx[i].xl = xl;
		jx[i].xr = xr;
		jx[i].yl = yl;
		jx[i].yr = yr;
		jx[i].s = s;
	}
}
signed main() {
	freopen("jxfg.in", "r", stdin);
	freopen("jxfg.out", "w", stdout);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		cin >> xi[i] >> yi[i];
	}
	add(1, 1);
	ans = 1000000001;
	dfs(2, 1, 0);
	cout << ans;
    return 0;
}