stdKonjac's Blog

 要做到不可替代,就要与众不同。

【连通块】

题目描述

一个点每过一个单位时间就会向 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分……

代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.