记录编号	22292	评测结果	AAAAAAAAAA
题目名称	扩散	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2010-11-18 15:13:58	内存使用	0.27 MiB

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

using namespace std;

const int oo=1000000000;
const int MAXN=55;

int n,x[MAXN],y[MAXN],i,j,k,a[MAXN][MAXN],ans=0;

void init()
{
	freopen("ppg.in","r",stdin);
	freopen("ppg.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			a[i][j]=(abs(x[i]-x[j])+abs(y[i]-y[j])+1)/2;
}

int main()
{
	init();
	for (k=1;k<=n;k++)
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				if (max(a[i][k],a[k][j])<a[i][j]) a[i][j]=max(a[i][k],a[k][j]);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if (a[i][j]>ans) ans=a[i][j];
	printf("%d\n",ans);
	return 0;
}