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

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=502;

int n,m,es=-1,i,j,k,tot=0,zhi[MAXN*MAXN],ans,l,r,mid;
int aa[MAXN],ab[MAXN],ba[MAXN],bb[MAXN],lim,mat[MAXN*2];
bool used[MAXN*2];

struct edge
{
	int t,c;
	edge *p;
}*v[MAXN],e[MAXN*MAXN];

inline void addedge(int i,int j,int c)
{
	e[++es].t=j; e[es].p=v[i]; e[es].c=c; v[i]=e+es;
	e[++es].t=i; e[es].p=v[j]; e[es].c=c; v[j]=e+es;
}

inline int cmp(const void *p,const void *q)
{
	return (*(int *)p)-(*(int *)q);
}

bool cp(int u)
{
	for (edge *x=v[u];x;x=x->p)
		if (x->c<=lim && !used[x->t])
		{
			used[x->t]=true;
			if (mat[x->t]==0 || cp(mat[x->t]))
			{
				mat[x->t]=u;
				return true;
			}
		}
	return false;
}

int main()
{
	freopen("christmas.in","r",stdin);
	freopen("christmas.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d%d",&aa[i],&ab[i]);
	for (i=1;i<=n;i++)
		scanf("%d%d",&ba[i],&bb[i]);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			zhi[++tot]=(aa[i]-ba[j])*(aa[i]-ba[j])+(ab[i]-bb[j])*(ab[i]-bb[j]);
			addedge(i,j+n,zhi[tot]);
			if (zhi[tot]>r) r=zhi[tot];
		}
	l=1;
	while (r>l)
	{
		lim=(r+l)>>1;
		ans=0;
		memset(mat,0,sizeof(mat));
		for (i=1;i<=n;i++)
		{
			memset(used,false,sizeof(used));
			if (cp(i)) ++ans;
		}
		if (ans!=n) l=lim+1;
		else r=lim;
	}
	printf("%d\n",lim);
	return 0;
}