#1254. 扩散

扩散

题目描述

一个点每过一个单位时间就会向四个方向扩散一个距离,如图。

两个点 aa、bb 连通,记作 e(a,b)e(a,b),当且仅当 a,ba,b 的扩散区域有公共部分。连通块的定义是块内的任意两个点 u,vu,v 都必定存在路径 e(u,a0),e(a0,a1),⋯ ,e(ak,v)e(u,a_0),e(a_0,a_1),\cdots,e(a_k,v)。给定平面上的 nn 个点,问最早什么时刻它们形成一个连通块。

输入格式

第一行一个正整数 NN,以下 NN 行,每行两个以空格分隔的正整数 Xi,YiX_i, Y_i,表示平面中一个点的坐标。

输出格式

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

样例

2
1 1
6 6
5

题目来源:洛谷 P1661