记录编号	70162	评测结果	AAAAAWW
题目名称	[NOIP 2002]矩形覆盖	最终得分	71
用户昵称	老师好~~~	是否通过	未通过
代码语言	C++	运行时间	0.055 s
提交时间	2013-09-24 19:19:46	内存使用	0.32 MiB

#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("jxfg.in");
ofstream fout("jxfg.out");
const int INF=99999999;
class woca
{
public:
	int x;
	int y;
}a[52];
int n,k;
bool cp(woca n,woca m)
{
	if(n.x<m.x)return 1;else return 0;
}
bool ck(woca n,woca m)
{
	if(n.y<m.y)return 1;else return 0;
}
int main()
{
	fin>>n>>k;
	int i,p;
	int b,c,d,e,f,j,h,q,w;
	int K=0,P=0,F=0;
	int ans=INF;
	woca flag[52];
	for(i=1;i<=51;i++)
		a[i].x=INF;
	for(i=1;i<=n;i++)
		fin>>a[i].y>>a[i].x;
	if(k==1)
	{
		sort(a+1,a+n+1,cp);
		b=a[n].x-a[1].x;
		sort(a+1,a+n+1,ck);
		c=a[n].y-a[1].y;
		fout<<b*c<<endl;
		return 0;
	}
	if(k==2)
	{
		sort(a+1,a+n+1,cp);
		for(i=1;i<=n;i++)
		{
			flag[i].x=a[i].x;
		    flag[i].y=a[i].y;
		}
		for(i=1;i<=n;i++)
		{
			while(a[++K].x<=a[i].x){}
			K--;
			if(K>=n)
				break;
			b=a[K].x-a[1].x;
			c=a[n].x-a[K+1].x;
			sort(flag+1,flag+K+1,ck);
			d=flag[K].y-flag[1].y;
			sort(flag+K+1,flag+n+1,ck);
			e=flag[n].y-flag[K+1].y;
			if(b*d+c*e<ans)
				ans=b*d+c*e;
			sort(flag+1,flag+n+1,cp);
		}
		fout<<ans<<endl;
		return 0;
	}
	if(k==3)
	{
		sort(a+1,a+n+1,cp);
		for(i=1;i<=n;i++)
		{
			flag[i].x=a[i].x;
		    flag[i].y=a[i].y;
		}
		for(i=1;i<=n;i++)
		{
			while(a[++K].x<=a[i].x){}
			K--;
			if(K>=n)
				break;
			P=K;
			b=a[K].x-a[1].x;
			sort(flag+1,flag+K+1,ck);
			f=flag[K].y-flag[1].y;
			for(p=i+1;p<=n;p++)
			{
			while(a[++P].x<=a[p].x){}
			P--;
			if(P>=n)
				break;
			c=a[P].x-a[K+1].x;
			sort(flag+K+1,flag+P+1,ck);
			j=flag[P].y-flag[K+1].y;
			sort(flag+P+1,flag+n+1,ck);
			d=a[n].x-a[P+1].x;
			h=flag[n].y-flag[P+1].y;
			if(b*f+c*j+d*h<ans)
				ans=b*f+c*j+d*h;
			sort(flag+1,flag+n+1,cp);
			}
		}
		fout<<ans<<endl;
	}
	if(k==4)
	{
		sort(a+1,a+n+1,cp);
		for(i=1;i<=n;i++)
		{
			flag[i].x=a[i].x;
		    flag[i].y=a[i].y;
		}	
		for(i=1;i<=n;i++)
		{
			while(a[++K].x<=a[i].x){}
			K--;
			if(K>=n)
				break;
			P=K;
			b=a[K].x-a[1].x;
			sort(flag+1,flag+n+1,cp);
			sort(flag+1,flag+K+1,ck);
			f=flag[K].y-flag[1].y;
			for(p=i+1;p<=n;p++)
			{
			while(a[++P].x<=a[p].x){}
			P--;
			F=P;
			if(P>=n)
				break;
			c=a[P].x-a[K+1].x;
			sort(flag+K+1,flag+P+1,ck);
			j=flag[P].y-flag[K+1].y;
			/////////////////////////OvO
			for(k=p+1;k<=n;k++)
			{
				while(a[++F].x<=a[k].x){}
				F--;
				if(F>=n)
					break;
				/////////////////
			    sort(flag+P+1,flag+F+1,ck);
			    d=a[F].x-a[P+1].x;
			    h=flag[F].y-flag[P+1].y;
				///////////////////
				sort(flag+F+1,flag+n+1,ck);
				q=a[n].x-a[F+1].x;
				w=flag[n].y-flag[F+1].y;
			    if(b*f+c*j+d*h+q*w<ans)
				ans=b*f+c*j+d*h+q*w;
			    sort(flag+1,flag+n+1,cp);
			}
		    }
		}
		fout<<ans<<endl;
	}		
	return 0;
}