记录编号	38425	评测结果	AAAAAA
题目名称	圣诞节	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.800 s
提交时间	2012-04-18 18:34:08	内存使用	1.23 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n,nar[501][2],nvr[501][2];
int q[501][501]={0},low,high,mid;
int link1[501]={0},used[501],ans=0;
bool check();
bool can(int t);
int main()
{
	freopen ("christmas.in","r",stdin);
	freopen ("christmas.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>nar[i][0]>>nar[i][1];
	}
	for (int i=1;i<=n;i++)
	{
		cin>>nvr[i][0]>>nvr[i][1];
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			q[i][j]=(nar[i][0]-nvr[j][0])*(nar[i][0]-nvr[j][0])+(nar[i][1]-nvr[j][1])*(nar[i][1]-nvr[j][1]);
			//cout<<q[i][j]<<' ';
		}
		//cout<<endl;
	}
	low=0;
	high=12500;
	while (low<high)
	{
		mid=((low+high)>>1);
		if (check())
		{
			high=mid;
			if (low==high)
				cout<<low;
		}
		else
		{
			low=mid+1;
			if (low==high)
				cout<<low;
		}
	}
	return 0;
}


bool check()
{
	ans=0;
	for (int i=1;i<=n;i++)
		link1[i]=-1;
	for (int i=1;i<=n;i++)
	{
		memset(used, 0, sizeof(used));
		if (can(i))
			ans++;
	}
	if (ans>=n)
		return true;
	else
		return false;
}

bool can(int t)
{
	for(int i=1;i<=n;i++)
	{
		if(!used[i]&&q[t][i]<=mid)
		{
			used[i]=true;
			if(link1[i]==-1||can(link1[i]))
			{
				link1[i]=t;
				return true;
			}
		}
	}
	return false;
}