问题 B: 2.扩散

问题 B: 2.扩散

题目描述

  一个点每过一个单位时间就会向 4 个方向扩散一个距离。两个点 a、b 连通,记做 e(a,b),当且仅当 a、 b 的扩散区域有公共部分。 连通块的定义是块内的任意两点 u、 都必定存在路径 e(u,a0),e(a0,a1),…,e(ak,v)。 v 给定平面上的 n 个点,问最早什么时刻它们形成一个连通块。



输入

第一行一个数 n,以下 n 行,每行一个点坐标。

输出

一个数,表示最早的时刻所有的点形成连通块。

样例输入输出

输入#1 复制
2
0 0
5 5
输出#1 复制
5

提示

【数据规模】
对于 20%的数据,满足 1≤N≤5,1≤x[i],Y[i] ≤50;
对于 100%的数据,满足 1≤N≤50;1≤X[i],Y[i]≤10^9。

序号 标题 作者 发表时间 费用 订购数 操作