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

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN=1005;
const int oo=~0u>>2;

struct Node
{
	int v,c;
	Node *next,*back;
	Node (){}
	Node (int _v,int _c,Node *_next,Node *_back=NULL):
		v(_v),c(_c),next(_next),back(_back){}
	void *operator new(size_t,void *p){return p;}
}*adj[MAXN],*cur[MAXN],pool[MAXN*MAXN*2],*mem=pool;

inline void addedge(int u,int v,int c)
{
	adj[u]=new (mem++)Node(v,c,adj[u]);
	adj[v]=new (mem++)Node(u,0,adj[v],adj[u]);
	adj[u]->back=adj[v];
}

int S,T;
int lv[MAXN];
bool label()
{
	queue<int> q;
	q.push(S);
	for(int i=S;i<=T;i++)
		lv[i]=-1;
	lv[S]=0;
	while(q.size())
	{
		int u=q.front();q.pop();
		for(Node *p=adj[u];p;p=p->next)
			if (p->c>0 && lv[p->v]==-1)
			{
				lv[p->v]=lv[u]+1;
				q.push(p->v);
				if (p->v==T)
					return true;
			}
	}
	return false;
}

int stack[MAXN],size;
Node *path[MAXN];
int maxflow;
void augment()
{
	stack[0]=S;
	size=1;
	for(int i=S;i<=T;i++)
		cur[i]=adj[i];
	while(size)
	{
		int u=stack[size-1];
		if (u!=T)
		{
			for(Node *&p=cur[u];p;p=p->next)
				if (p->c>0 && lv[p->v]==lv[u]+1)
				{
					stack[size]=p->v;
					path[size++]=p;
					break;
				}
			if (cur[u]==NULL)
				size--,lv[u]=-1;
		}
		else
		{
			int delta=oo,k=-1;
			for(int i=1;i<size;i++)
				if (path[i]->c<delta)
					delta=path[i]->c,k=i;
			for(int i=1;i<size;i++)
				path[i]->c-=delta,
				path[i]->back->c+=delta;
			maxflow+=delta;
			size=k;
		}
	}
}

void dinic()
{
	maxflow=0;
	while(label())
		augment();
}

int N;
int w[MAXN][MAXN];
bool check(int mid)
{
	mem=pool;
	for(int i=S;i<=T;i++)
		adj[i]=NULL;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			if (w[i][j]<=mid)
				addedge(i+1,j+1+N,1);
	for(int i=0;i<N;i++)
	{
		addedge(S,i+1,1);
		addedge(i+1+N,T,1);
	}
	dinic();
	return maxflow==N;
}

inline int sqr(int x)
{
	return x*x;
}

int X1[MAXN],X2[MAXN],Y1[MAXN],Y2[MAXN];
int main()
{
	freopen("christmas.in","r",stdin);
	freopen("christmas.out","w",stdout);
	scanf("%d",&N);
	S=0,T=2*N+1;
	for(int i=0;i<N;i++)
		scanf("%d%d",X1+i,Y1+i);
	for(int i=0;i<N;i++)
		scanf("%d%d",X2+i,Y2+i);
	int l=oo;
	int r=0;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
			w[i][j]=sqr(X1[i]-X2[j])+sqr(Y1[i]-Y2[j]);
		l=min(l,*min_element(w[i],w[i]+N));
		r=max(r,*max_element(w[i],w[i]+N));
	}
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if (check(mid))
			r=mid;
		else
			l=mid+1;
	}
	if (l==r || check(l)) printf("%d\n",l);
	else printf("%d\n",r);
	return 0;
}