```c
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int n,x[55],y[55],max=-9999999,f[55];
int sum(int a,int b)
{
if(a-b>0) return a-b;
else return b-a;
}
int fa(int g)
{
if(f[g]==g) return g;
return fa(f[g]);
}
int main(int argc, char *argv[]) {
int i,j,l,r,mid,temp,na,nb,cou=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&x[i],&y[i]);
}
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(sum(x[i],x[j])+sum(y[i],y[j])>max) max=sum(x[i],x[j])+sum(y[i],y[j]);
}
}
l=0;
r=max;
while(l<=r)
{
for(i=1;i<=n;i++)
f[i]=i;
mid=(l+r)/2;
cou=0;
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if((sum(x[i],x[j])+sum(y[i],y[j]))/2<=mid)
{
na=fa(i);
nb=fa(j);
if(na!=nb)
f[na]=nb;
}
}
}
for(i=1;i<=n;i++)
if(f[i]==i) cou++;
if(cou==1)
{
temp=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d",temp);
return 0;
}
```
by limarks @ 2018-10-05 15:52:38