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

#include <fstream>

#define I_F "ppg.in"
#define O_F "ppg.out"
#define MAX 50

using namespace std;

short n;
long x[MAX],y[MAX];
long map[MAX][MAX];
long ans;

long Abs(long x);
long Max(long a, long b);
void Input();
void Ycl();
void Floyd();
void Search();
void Output();

int main()
{
	Input();
	Ycl();
	Floyd();
	Search();
	Output();
	return 0;
}

long Abs(long x)
{
	if (x>0)
		return x;
	else
		return (-x);
}

long Max(long a, long b)
{
	if (a>b)
		return a;
	else
		return b;
}

void Input()
{
	ifstream fin(I_F);
	fin>>n;
	for (short i=0; i<n; fin>>y[i++])
		fin>>x[i];
	fin.close();
}

void Ycl()
{
	short i,j;
	for (i=0; i<n; i++)
		for (j=0; j<n; j++)
		{
			map[i][j]=(Abs(x[i]-x[j])+Abs(y[i]-y[j])+1)/2;
			map[j][i]=map[i][j];
		}
}

void Floyd()
{
	short i,j,k;
	for (k=0; k<n; k++)
		for (i=0; i<n; i++)
			for (j=0; j<n; j++)
				if (Max(map[i][k],map[k][j])<map[i][j])
					map[i][j]=Max(map[i][k],map[k][j]);
}

void Search()
{
	short i,j;
	for (i=0; i<n; i++)
		for (j=0; j<n; j++)
			if (map[i][j]>ans)
				ans=map[i][j];
}

void Output()
{
	ofstream fout(O_F);
	fout<<ans<<'\n';
	fout.close();
}