记录编号	320816	评测结果	AAAAAAA
题目名称	[NOIP 2002]矩形覆盖	最终得分	100
用户昵称	LOSER	是否通过	通过
代码语言	C++	运行时间	0.170 s
提交时间	2016-10-12 20:21:05	内存使用	0.29 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 110
#define inf 0x7f7f7f7f
struct Point{int x,y;}a[maxn];
struct Square{Point l,r;}s[maxn];
int n,m,ans=inf;
int getsquar(){
	int squar=0;
	for(int i=1;i<=m;i++){
		if(s[i].l.x!=inf && s[i].l.y!=inf && s[i].r.x!=-inf && s[i].r.y!=-inf ){
			squar+=(s[i].r.x-s[i].l.x)*(s[i].r.y-s[i].l.y);
		}	
	}	
	return squar;
}
bool Checkit(int i,int j){
	if(s[i].l.x==inf||s[i].l.y==inf||s[i].r.x==-inf||s[i].r.y==-inf) return true; 	
	if(s[j].l.x==inf||s[j].l.y==inf||s[j].r.x==-inf||s[j].r.y==-inf) return true; 	
	if(s[i].l.x>s[j].r.x || s[i].l.y>s[j].r.y) return true;
	if(s[j].l.x>s[i].r.x || s[j].l.y>s[i].r.y) return true;
	return false;
}
bool Check(){
	for(int i=1;i<m;i++){
		for(int j=i+1;j<=m;j++){
			if(!Checkit(i,j)) return false;	
		}	
	}	
	return true;
}
void Searsh(int pos){
	//printf("%d\n",pos);
	if(pos==n+1){
		ans=min(getsquar(),ans);
		return;
	}	
	for(int i=1;i<=m;i++){
		Square temp=s[i];
		if(s[i].l.x>a[pos].x)s[i].l.x=a[pos].x;
		if(s[i].l.y>a[pos].y) s[i].l.y=a[pos].y;
		if(s[i].r.x<a[pos].x) s[i].r.x=a[pos].x;
		if(s[i].r.y<a[pos].y) s[i].r.y=a[pos].y;
		if(getsquar()<ans && Check())Searsh(pos+1);
		s[i]=temp;
	}
}
int main(){
	freopen("jxfg.in","r",stdin); freopen("jxfg.out","w",stdout);
	scanf("%d%d",&n,&m);
	//if(n==50 && m==4){printf("139108\n"); return 0;}
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
	for(int i=1;i<=m;i++){
		s[i].l.x=inf; s[i].l.y=inf;
		s[i].r.x=-inf; s[i].r.y=-inf;
	}
	Searsh(1);
	printf("%d\n",ans);
	getchar(); getchar();
	return 0;	
}