记录编号	235646	评测结果	AAAAAAAAAA
题目名称	扩散	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-03-11 10:48:37	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
int n,mst=0;
int read(){
	int x;char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!=EOF);
	if(ch==EOF)return -1;
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return x;
}
int dis[52][52];
int x[52],y[52];
int abs(int x){
	return x<0?-x:x;
}
struct node{
	int v,d;
	bool operator <(const node &a)const{
		return d>a.d;
	}
	node(int _v,int _d){
		v=_v;d=_d;
	}
};
bool linked[55];
int d[55];
void prim(){
	memset(d,63,sizeof(d));
	linked[0]=true;
	for(int i=1;i<n;++i)d[i]=dis[0][i];
	for(int i=1;i<n;++i){
		int minv=53;
		for(int k=0;k<n;++k){
			if(!linked[k]&&d[k]<d[minv])minv=k;
		}
		linked[minv]=true;
		if(d[minv]>mst)mst=d[minv];
		for(int k=0;k<n;++k){
			if(!linked[k]&&dis[minv][k]<d[k])d[k]=dis[minv][k];
		}
	}
}
int main(){
	freopen("ppg.in","r",stdin);
	freopen("ppg.out","w",stdout);
	n=read();
	for(int i=0;i<n;++i){
		x[i]=read();y[i]=read();
	}
	for(int i=0;i<n;++i)
		for(int j=i+1;j<n;++j)
			{
				
				dis[i][j]=dis[j][i]=(abs(x[i]-x[j])+abs(y[i]-y[j])+1)>>1;
	//			printf("%d-%d:%d\n",i,j,dis[i][j]);
			}
	prim();
	printf("%d",mst);
	fclose(stdin);fclose(stdout);
	return 0;
}