记录编号	26302	评测结果	WWWWWW
题目名称	圣诞节	最终得分	0
用户昵称	PurpleShadow	是否通过	未通过
代码语言	C++	运行时间	0.002 s
提交时间	2011-07-23 16:00:58	内存使用	2.19 MiB

#include <cstdio>
#include <cstring>
const int N=501;
struct node
{int H,A;};
int n;
node M[N],W[N];
void init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%d%d",&M[i].H,&M[i].A);
	for (int i=1;i<=n;++i)
		scanf("%d%d",&W[i].H,&W[i].A);
}
inline int Weight(node a,node b)
{return (a.H-b.H)*(a.H-b.H)+(a.A-b.A)*(a.A-b.A);}
struct edge
{int adv,next;};
edge es[N*N];
int g[N],e;
inline void addedge(int a,int b)
{
	es[++e].adv=b;
	es[e].next=g[a];
	g[a]=e;
}
int q[N],dx[N],dy[N],mx[N],my[N];
bool bfs()
{
	memset(dx,0,sizeof(dx));
	memset(dy,0,sizeof(dy));
	int h=0,r=0,i,j,v;
	for (i=1;i<=n;++i)
		if (!mx[i]) q[++r]=i;
	bool find=0;
	while (h<r)
	{
		i=q[++h];
		for (j=g[i];j;j=es[j].next)
			if (!dy[v=es[j].adv])
			{
				dy[v]=dx[i]+1;
				if (!my[v]) find=1;else
				{
					dx[my[v]]=dy[v]+1;
					q[++r]=my[v];
				}
			}
	}
	return find;
}
bool dfs(int u)
{
	int v,j;
	for (j=g[u];j;j=es[j].next)
		if (dy[v=es[j].adv]==dx[u]+1)
		{
			dy[v]=0;
			if (!my[v]||dfs(my[v]))
			{
				mx[u]=v;
				my[v]=u;
				return 1;
			}
		}
	return 0;
}			
int getAns(int m)
{
	memset(g,0,sizeof(g));e=0;
	int i,j;
	for (i=1;i<=n;++i)
	for (j=1;j<=n;++j)
		if (Weight(M[i],W[j])<=m) addedge(i,j);
	memset(mx,0,sizeof(mx));
	memset(my,0,sizeof(my));
	int ans=0;
	while (bfs())
		for (int i=1;i<=n;++i)
			if (!mx[i]&&dfs(i)) ++ans;
	return ans;
}
void slove()
{
	int l=-1,r=12501,mid;
	while (l!=r-1)
	{
		mid=(l+r)>>1;
		if (getAns(mid)==n) r=mid;else l=mid;
	}
	printf("%d\n",r);
}
int main()
{
freopen("christmas.in","r",stdin);
freopen("christmas.out","w",stdout);
	init();
	slove();
	return 0;
}