扩散
题目描述
一个点每过一个单位时间就会向四个方向扩散一个距离,如图。
![](https://cdn.luogu.com.cn/upload/image_hosting/cd4e53lw.png)
两个点 $a$ 、 $b$ 连通,记作 $e(a,b)$,当且仅当 $a,b$ 的扩散区域有公共部分。连通块的定义是块内的任意两个点 $u,v$ 都必定存在路径 $e(u,a_0),e(a_0,a_1),\cdots,e(a_k,v)$。给定平面上的 $n$ 给点,问最早什么时刻它们形成一个连通块。
输入输出格式
输入格式
第一行一个数 $n$,以下 $n$ 行,每行一个点坐标。
输出格式
一个数,表示最早的时刻所有点形成连通块。
输入输出样例
输入样例 #1
2
0 0
5 5
输出样例 #1
5
说明
### 数据范围及约定
对于 $20\%$ 的数据,满足 $1 \le N \le 5;1 \le X_i,Y_i \le 50$。
对于 $100\%$ 的数据,满足 $1 \le N \le 50$,$1 \le X_i,Y_i \le 10^9$。