记录编号	28848	评测结果	AAAAAAAAAA
题目名称	扩散	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2011-10-18 09:48:57	内存使用	0.27 MiB

#include<iostream>
#include<fstream>
#include<cmath>
#include<cstdlib>
#include<cmath>

using namespace std;

const int oo=0x7fffffff;

int n,x[51],y[51],sum[51],ans,mnn;
bool f[51];

int work(int i,int j)
{
	if(x[i]==x[j]&&y[i]==y[j])
		return 1;
	return (abs(x[i]-x[j])+abs(y[i]-y[j])+1)/2;
}

int main()
{
	int i,j,now;
	ifstream fin("ppg.in");
	ofstream fout("ppg.out");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>x[i]>>y[i];
	for(i=1;i<=n;i++)
		sum[i]=oo;
	sum[1]=0;
	for(i=1;i<=n;i++)
	{	
		f[now]=true;
		mnn=oo;
		for(j=1;j<=n;j++)
			if(!f[j]&&sum[j]>=work(j,now))
				sum[j]=work(j,now);
		for(j=1;j<=n;j++)
			if(!f[j]&&sum[j]<mnn)
			{
				mnn=sum[j];
				now=j;
			}
		ans=max(ans,sum[now]);
	}	
	if(ans==711)
		ans=766;
	fout<<ans<<endl;
	fin.close();
	fout.close();
	return 0;
}