记录编号	33011	评测结果	AAAAAAAAAA
题目名称	扩散	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2011-11-09 08:21:48	内存使用	0.30 MiB

#include <cstdio>
using namespace std;

int que[50]={0},inf[50][2]={{0}},map[50][50]={{0}};
//bool used[50]={false};

int absint(int a)
{
	if (a<0)
		return(-a);
	else
		return(a);
}

void swap(int& a,int& b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

int main(void)
{
	freopen("ppg.in","r",stdin);
	freopen("ppg.out","w",stdout);
	int i,j,n,now,temp,tempj/*,usednum=1*/,maxnum=0;
	scanf("%d\n",&n);
	for (i=0;i<n;i++)
	{
		scanf("%d %d\n",&inf[i][0],&inf[i][1]);
		for (j=i-1;j>=0;j--)
		{
			temp=(absint(inf[i][0]-inf[j][0])+absint(inf[i][1]-inf[j][1])+1)/2;
			if (temp<map[i][j]||map[i][j]==0)
			{
				map[i][j]=temp;
				map[j][i]=temp;
			}
		}
	}
	for (i=0;i<n;i++)
		que[i]=i;
//	used[0]=true;
	for (now=0;now<n-1;now++)
	{
		temp=2000000000;
		for (i=0;i<=now;i++)
			for (j=now+1;j<n;j++)
				if (map[que[i]][que[j]]<temp)
				{
					temp=map[que[i]][que[j]];
					tempj=j;
				}
		swap(que[now+1],que[tempj]);
		if (temp>maxnum)
			maxnum=temp;
	}
	printf("%d\n",maxnum);
/*	temp=0;
	for (i=0;i<n;i++)
		for (j=i+1;j<n;j++)
			if (temp<map[i][j])
				temp=map[i][j];*/
	fclose(stdin);
	fclose(stdout);
	return(0);
}