记录编号	38421	评测结果	AAAAAT
题目名称	圣诞节	最终得分	83
用户昵称	Makazeu	是否通过	未通过
代码语言	C++	运行时间	1.041 s
提交时间	2012-04-18 18:20:25	内存使用	0.21 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 501
using namespace std;
int Age[MAXN*2],H[MAXN*2];
int Mat[MAXN],Used[MAXN];
int Diff[MAXN][MAXN];
int N,P,X;
int ans;
inline void init()
{
	scanf("%d\n",&N); P=N*2;
	for(int i=1;i<=P;i++) scanf("%d %d\n",&H[i],&Age[i]);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			Diff[i][j]=(Age[i]-Age[j+N])*(Age[i]-Age[j+N])+(H[i]-H[j+N])*(H[i]-H[j+N]);
}
 
bool cross(int k)
{
	int v;
	for(int i=1;i<=N;i++)
	{
		if(Diff[k][i]>X) continue;
		if(Used[i]) continue;
		Used[i]=1;
		if(!Mat[i] || cross(Mat[i]))
		{
			Mat[i]=k;
			return true;
		}
	}
	return false;
}
 
inline bool hungary()
{
	int Ans=0;
	for(int i=1;i<=N;i++)
	{
		memset(Used,0,sizeof(Used));
		Ans+=cross(i);
	}
	return Ans==N;
}
 
inline void binarysearch()
{
	int l=0,r=12500,mid;
	while(l<=r)
	{
		mid=(l+r)>>1;
		X=mid;
		memset(Mat,0,sizeof(Mat));
		if(hungary()) r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d\n",ans); 
}
 
int main()
{
	freopen("christmas.in","r",stdin);
	freopen("christmas.out","w",stdout);
	init();
	binarysearch();
	return 0;
}