luogu#P1661. 扩散

扩散

题目描述

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

两个点 aabb 连通,记作 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 行,每行一个点坐标。

输出格式

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

2
0 0
5 5
5

提示

数据范围及约定

对于 20%20\% 的数据,满足 1N5;1Xi,Yi501 \le N \le 5;1 \le X_i,Y_i \le 50

对于 100%100\% 的数据,满足 1N501 \le N \le 501Xi,Yi1091 \le X_i,Y_i \le 10^9