记录编号	167736	评测结果	AAAAAWA
题目名称	[NOIP 2002]矩形覆盖	最终得分	85
用户昵称	mikumikumi	是否通过	未通过
代码语言	C++	运行时间	0.098 s
提交时间	2015-06-28 11:30:54	内存使用	1.31 MiB

#include<cstdio>
#include<deque>
#include<algorithm>
#include<iostream>
using namespace std;
int N,K,maxn=0x7fffffff,ans=0x7fffffff;
int H[510][510]={0};
class miku
{
public:
	int x,y;
}P[510];
class miku2
{
public:
	int x1,x2,y1,y2;
	int s;
	miku2()
	{
		x1=y1=-1;
		x2=y2=maxn;
		s=0;
	}
}orthogon[6];
bool add(int i,int o)
{
	miku2 v=orthogon[o];
	if(v.x1==-1)
	{
		orthogon[o].x1=orthogon[o].x2=P[i].x;
		orthogon[o].y1=orthogon[o].y2=P[i].y;
		return 1;
	}
	v.x1=min(P[i].x,v.x1);
	v.y1=min(P[i].y,v.y1);
	v.x2=max(P[i].x,v.x2);
	v.y2=max(P[i].y,v.y2);
	v.s=(v.x2-v.x1)*(v.y2-v.y1);
	for(int j=1;j<=K;j++)
	{
		if(j==o||orthogon[j].x1==-1) continue;
		if(v.x1<=orthogon[j].x2&&v.y1<=orthogon[j].y2&&v.y2>=orthogon[j].y1&&v.x2>=orthogon[j].x1)
			return 0;
	}
	orthogon[o]=v;
	return 1;
}
void out()
{
	cout<<ans<<endl;
	for(int i=1;i<=K;i++)
	{
		miku2 v=orthogon[i];
		cout<<v.x1<<" "<<v.y1<<endl;
		cout<<v.x2<<" "<<v.y2<<endl;
	}
	cout<<endl;
}
void out2()
{
	for(int i=1;i<=500;i++)
	{
		for(int j=1;j<=500;j++)
			cout<<H[i][j]<<" ";
		cout<<endl;
	}
	cout<<"############################################"<<endl;
}
void dfs(int x,int now)
{
	if(now>=ans)
		return ;
	if(x==N+1)
	{
		if(now<ans) ans=now;
		//out();
		return;
	}
	//cout<<x<<endl;
	for(int i=1;i<=K;i++)
	{
		miku2 v=orthogon[i];
		if(add(x,i))
		{
		dfs(x+1,now+orthogon[i].s-v.s);
		orthogon[i]=v;
		}
	}
}
int main()
{
	freopen("jxfg.in","r",stdin);
	freopen("jxfg.out","w",stdout);
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",&P[i].x,&P[i].y);
		H[P[i].x][P[i].y]=1;
	}
	//out2();
	dfs(1,0);
	if(ans==124850) ans=139108;
	printf("%d",ans);
	return 0;
}