【连通块】

题目描述

一个点每过一个单位时间就会向 4 个方向扩散一个距离,如下图所示:

(一个点每过一个单位时间向四个方向扩散一个距离)

两个点 a、b 连通,记作 e(a,b),当且仅当 a、b 的扩散区域有公共部分。连通块的定义是块内的任意两点 u、v 都必定存在路径 e(u,a0),e(a0,a1),…,e(ak,v)。

给定平面上的 n 个点,问最早什么时刻它们形成一个连通块。

输入格式

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

输出格式

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

样例数据 1

输入

2
0 0
5 5

输出

5

备注

【数据范围】
对于 20% 的数据,满足:1≤N≤5;0≤X[i],Y[i]≤50;
对于 100% 的数据,满足:1≤N≤50;0≤X[i],Y[i]≤109

直接对每两个点求一遍曼哈顿距离,如果是奇数还要+1(奇数的时候扩散出去位置是错开的,要再多1秒) 然后搞一遍MST求最长边即可,真不知道当时怎么想的乱搞了个Floyed骗了40分……

代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*