#P1661. 扩散
扩散
题目描述
一个点每过一个单位时间就会向四个方向扩散一个距离,如图。
两个点 、 连通,记作 ,当且仅当 的扩散区域有公共部分。连通块的定义是块内的任意两个点 都必定存在路径 。给定平面上的 个点,问最早什么时刻它们形成一个连通块。
输入格式
第一行一个数 ,以下 行,每行一个点坐标。
输出格式
一个数,表示最早的时刻所有点形成连通块。
2
0 0
5 5
5
提示
数据范围及约定
对于 的数据,满足 。
对于 的数据,满足 ,。
一个点每过一个单位时间就会向四个方向扩散一个距离,如图。
两个点 a 、 b 连通,记作 e(a,b),当且仅当 a,b 的扩散区域有公共部分。连通块的定义是块内的任意两个点 u,v 都必定存在路径 e(u,a0),e(a0,a1),⋯,e(ak,v)。给定平面上的 n 个点,问最早什么时刻它们形成一个连通块。
第一行一个数 n,以下 n 行,每行一个点坐标。
一个数,表示最早的时刻所有点形成连通块。
2
0 0
5 5
5
对于 20% 的数据,满足 1≤N≤5;1≤Xi,Yi≤50。
对于 100% 的数据,满足 1≤N≤50,1≤Xi,Yi≤109。