记录编号	38449	评测结果	AAAAAA
题目名称	圣诞节	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.898 s
提交时间	2012-04-19 08:17:14	内存使用	9.02 MiB

#include<fstream>
#include<memory.h>
#include<stdlib.h>
#include<algorithm>
#define MAXN 501
using namespace std;
int Mat[MAXN],Used[MAXN];
int map[1010][1010],mapa[1010][1010];
int a[250000];
int boyh[501],boya[510],girlh[510],girla[510];
int d[1010]={-1};
int n,m,i,j,k,l,r,mid;
int X;
bool v[510];
bool cross(int k) 
{     
	int v;     
	for(int i=1;i<=n;i++)     
	{         
		if(map[k][i]>X) 
			continue;         
		if(Used[i]) continue;         
		Used[i]=1;         
		if(!Mat[i] || cross(Mat[i]))         
		{             
			Mat[i]=k;             
			return true;         
		}     
	}
	return false; 
}
bool cmp(int a,int b)
{
	return a<b;
}
/*void sort(int l,int r) 
{     
	int i=l,j=r,x=sa[i+j>>1],y;     
	while (i<=j)     
	{         
		while (zt[x]>zt[sa[i]]||(zt[x]==zt[sa[i]]&&ud[x]>ud[sa[i]])) i++;         
		while (zt[x]<zt[sa[j]]||(zt[x]==zt[sa[j]]&&ud[x]<ud[sa[j]])) j--;         
		if (i<=j)         
		{             
			y=sa[i]; 
			sa[i]=sa[j]; 
			sa[j]=y;             
			i++; j--;         
		}     
	}     
	if (i<r) sort(i,r);     
	if (l<j) sort(l,j); 
} */
inline bool hungary() 
{     
	int Ans=0;     
	for(int i=1;i<=n;i++)     
	{         
		memset(Used,0,sizeof(Used));         
		Ans+=cross(i);     
	}     
	return Ans==n; 
} 
int main()
{
	ifstream fin("christmas.in");
	ofstream fout("christmas.out");
	fin>>n;
	for (i=1;i<=n;i++)
		fin>>boyh[i]>>boya[i];
	for (i=1;i<=n;i++)
		fin>>girlh[i]>>girla[i];
	m=2*n;
	int p=0;
	memset(map,0,sizeof(map));
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			map[i][j]=(boyh[i]-girlh[j])*(boyh[i]-girlh[j])+(boya[i]-girla[j])*(boya[i]-girla[j]);
			p++;
			a[p]=map[i][j];
		}
		sort(a+1,a+p+1);
	for (i=1;i<=m;i++)
		for (j=1;j<=m;j++)
			mapa[i][j]=map[i][j];
	l=1;r=p;
	mid=(l+r) / 2;
	X=a[mid];
	while (l<r)
	{
		memset(Mat,0,sizeof(Mat));
		if (hungary())
		{
			r=mid;
			mid=(l+r) / 2;
			X=a[mid];
		}
		else
		{
			l=mid+1;
			mid=(l+r) / 2;
			X=a[mid];
		}
	}
	fout<<a[l];
	fin.close();
	fout.close();
	return 0;
}

/*bool find(int k)
{
	int i;
	int al=1;
	int br=n;
	if (k<=br)
	{
		al=al+n;
		br=br+n;
	}
	for (i=al;i<=br;i++)
	{
		if ((map[k][i]>0)and(map[k][i]<=a[mid])) 
			if (d[i]==-1)
		{
			d[k]=i;
			d[i]=k;
			map[i][k]=map[k][i];
			map[k][i]=0;
			return true;
		}else{
			if (v[i]==true)
			{v[i]=false;
				if (find(i))
				{
					v[i]=false;
					d[k]=i;
					map[i][k]=map[k][i];
					map[k][i]=0;
				    return true;
				}
			}
		}
	}
	return false;
}
bool tg(int x)
{
	int sum=0;
	for (i=1;i<=n+n;i++)
		d[i]=-1;
	for (int i=1;i<=n;i++)
	{
		if (d[i]==-1)
		{
			if (find(i))
				sum++;
			memset(v,true,sizeof(v));
		}
	}
	for (int ii=1;ii<=n+n;ii++)
		for(int jj=1;jj<=n+n;jj++)
			map[ii][jj]=mapa[ii][jj];
		sum=0;
	for (int ii=1;ii<=n;ii++)
		if (d[ii]!=-1) sum++;
	if (sum==n)
	{
		return true;
	}else{
		return false;
	}
}*/