记录编号	22285	评测结果	AAAAAAAAAA
题目名称	扩散	最终得分	100
用户昵称	郭乾乐	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2010-11-18 14:46:38	内存使用	0.26 MiB

#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;

int maxx(int a,int b)
{
	if(a>b) return a;
	else return b;
}

int main()
{
	ifstream fin("ppg.in");
	ofstream fout("ppg.out");
	int n,f[100][100],x[100],y[100],i,j,k,t;
	fin>>n;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			f[i][j]=99999999;
	for(i=1;i<=n;i++)
		fin>>x[i]>>y[i];
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
		{
			t=abs(x[i]-x[j])+abs(y[i]-y[j]);
			if(t%2==0)
				t=t/2;
			else
				t=t/2+1;
			f[i][j]=t;
			f[j][i]=t;
		}
	for(i=1;i<=n;i++)
		f[i][i]=0;
	for(k=1;k<=n;k++)
	    for(i=1;i<=n;i++)
		    for(j=1;j<=n;j++)
				if(f[i][j]>maxx(f[i][k],f[k][j]))
					f[i][j]=maxx(f[i][k],f[k][j]);
    int maxn=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(f[i][j]>maxn)
				maxn=f[i][j];
	fout<<maxn<<endl;
	return 0;
}