6519 - 扩散
时间限制 : 1 秒
内存限制 : 128 MB
一个点每过一个单位时间就会向4个方向扩散一段距离，如图1-2-3所示：两个点a、b连通，记作e（a,b），当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e（u，a1），e（a0，a1）…e（ak，v）。给定平面上的n个点，问最早什么时候它们能形成一个连通块？
输入
第一行一个数n，以下n行，每行表示一个点坐标。
输出
输出仅一个数，表示所有点形成连通块的最早时刻。
样例
输入
2 0 0 5 5
输出
5
提示
对于20%的数据，满足1≤n≤50，1≤X[i]，Y[i]≤50。
对于100%的数据，满足1≤n≤50，1≤X[i]，Y[i]≤10^9
来源
一本通提高