记录编号	22302	评测结果	AAAAAAAAAA
题目名称	扩散	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	Pascal	运行时间	0.002 s
提交时间	2010-11-18 15:39:31	内存使用	0.17 MiB

program ppg;
const oo=2000000000;
var n,i,j,s,p,w:longint;
  X,Y,D:array[0..51]of longint;
  B:array[0..51]of boolean;
function Dis(i,j:longint):longint;
var k:longint;
begin
  if (X[i]=X[j])and(Y[i]=Y[j]) then exit(1);
  k:=abs(X[i]-X[j])+abs(Y[i]-Y[j]);
  if k mod 2=0 then exit(k div 2) else exit(k div 2 +1);
end;
begin
  assign(input,'ppg.in'); reset(input);
  assign(output,'ppg.out'); rewrite(output);
  readln(n);
  for i:=1 to n do readln(X[i],Y[i]);
  for i:=1 to n do D[i]:=oo;
  D[1]:=0; p:=1; s:=0;
  for j:=1 to n do
  begin
    B[p]:=true; w:=oo;
    for i:=1 to n do
      if (not B[i])and(D[i]>=Dis(i,p))
        then D[i]:=Dis(i,p);
    for i:=1 to n do
      if (not B[i])and(D[i]<=w)
        then begin w:=D[i]; p:=i; end;
    if s<D[p] then s:=D[p];
  end;
  writeln(s);
  close(input); close(output);
end.