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

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

using namespace std;

const int oo=1000000000;

struct point
{
	int x,y;
}P[1111];

int cn;
struct dis
{
	int x,y,dis;
}cost[255555];

bool cmp(const dis &a,const dis &b)
{
	return a.dis < b.dis;
}

int n;

void init()
{
	scanf("%d",&n);
	for (int i=1;i<=2*n;i++)
	scanf("%d%d",&P[i].x,&P[i].y);
	for (int i=1;i<=n;i++)
	for (int j=n+1;j<=2*n;j++)
	{
		cost[++cn].x=i;cost[cn].y=j;
		cost[cn].dis=(P[i].x-P[j].x)*(P[i].x-P[j].x)+(P[i].y-P[j].y)*(P[i].y-P[j].y);
	}
	sort(cost+1,cost+cn+1,cmp);
}

struct edge
{
	int t,c;
	edge *next,*op;
}E[888888],*V[1111];
int eh;
inline void addedge(int a,int b,int c)
{
	E[++eh].next=V[a];  V[a]=E+eh;  V[a]->t=b;  V[a]->c=c;
	E[++eh].next=V[b];  V[b]=E+eh;  V[b]->t=a;  V[b]->c=0;
	V[a]->op=V[b];  V[b]->op=V[a];
}

int ansflow,S,T,pn;
int d[1111],vd[1111];
int dfs(int u,int flow)
{
	if (u==T) return flow;
	int now=0;
	for (edge *e=V[u];e;e=e->next)
	if (e->c && d[e->t]+1==d[u])
	{
		int t=dfs(e->t,min(flow-now,e->c));
		e->c -= t;
		e->op->c += t;
		now += t;
		if (now==flow) return now;
	}
	if (d[S]>=pn) return now;
	if (--vd[d[u]]==0) d[S]=pn;
	vd[++d[u]]++;
	return now;
}

void SAPflow()
{
	d[S]=3;d[T]=0;
	for (int i=1;i<=n;i++) d[i]=2,d[i+n]=1;
	vd[3]=vd[0]=1;vd[2]=vd[1]=n;
	while (d[S]<pn)
	{
		ansflow+=dfs(S,oo);
	}
}

int check1()
{
	int lim=0;
	for (int i=1;i<=cn;i++)
	{
		addedge(cost[i].x,cost[i].y,cost[i].dis);
		if ( i % n == 0 )
		{
			SAPflow();
			if (ansflow==n) {lim=i;break;}
		}
	}
	lim-=n;eh=0;memset(V,0,sizeof(V));ansflow=0;
	for (int i=1;i<=lim;i++) 
	addedge(cost[i].x,cost[i].y,cost[i].dis);
	for (int i=1;i<=n;i++)
	{
		addedge(S,i,1);
		addedge(i+n,T,1);
	}
	return lim;
}

int check2(int lim)
{
	for (int i=lim+1;i<=lim+n;i++)
	{
		addedge(cost[i].x,cost[i].y,cost[i].dis);
		SAPflow();
		if (ansflow==n) return cost[i].dis;
	}
	return 0;
}

void solve()
{
	S=0;T=2*n+1;pn=2*n+2;
	for (int i=1;i<=n;i++)
	{
		addedge(S,i,1);
		addedge(i+n,T,1);
	}
	printf( "%d\n" , check2(check1()) );
}

int main()
{
	freopen("christmas.in","r",stdin);
	freopen("christmas.out","w",stdout);
	init();
	solve();
	return 0;
}