★实验任务
在二维坐标系x-y上有N座城镇，由于交通不便，身为市长的Itnod决定修建公路以连
接这N座城镇，方法如下：
在起始时间，不存在任何公路，但在接下来的每一单位时间内，每座城镇都向自己的
东、西、南、北四个方向各修出一单位长度的公路，当两座不同的城镇的公路有交点时，即为
连通的，连通性是可传递的（例如a城镇与b城镇连通，b城镇与c城镇连通，则a城镇与
c城镇连通）。
Itnod不知道什么时候所有城镇才能连通，于是请你来写一个程序，算出所有城镇连通
的时间T。
★数据输入
第一行为N（1<=N<=50），接下来的N 行中，每行都包含两个整数x，y（-
1000000<x,y<1000000），数据保证不会出现相同的两个坐标。
★数据输出
输出只有一行，包含时间T。
输入示例
2
0 0
5 5
输出示例
5

作业题目呀，完全没有思路，求高手指教，还有，下面是助教发来的提示：
可以通过枚举时间，在这一时间的前提下，判断某两点是否连通，从而得到一个图，只要这个图是连通的，这个时间T就符合条件。至于枚举时间的方法，O(log(2000000))或者O(10000)应该都行。
没看明白，求各位大侠帮帮忙，理下思路……

助教的意思就是让时间从小往大变：比如看看1秒之后能不能把所胡城镇全连通，如果能那么1秒就是要的时间，如果不能就看2秒能不能。直到全部连通时，用的时间就是所求的时间。

然后剩下的任务就是判断一个具体的时间上，某两个城镇是不是连通的。
两个城镇坐标如果是 (x1, y1), (x2, y2) 的话，那么它们在 min(|x2-x1|, |y2-y1|) 秒后一定会连通。

判断连通可以用下面的方法：
假如有5个城镇，ABCDE。你可以建一个表，
A 1
B 2
C 3
D 4
E 5
如果，某一个时刻某两个城镇连通了，你就把它们的编号设成统一的。比如过了一段时间，A与B连通了，C与D连通了，剩下之间都没连通。
那么表就会变成：
A 1
B 1
C 3
D 3
E 5
现在如果一个某一个连通子图中的某一个点和另一个图中的某一个点连通了，那么这两个子图中的全部点都是连通的。
比如又过一些时候，A或B中的某一个和E连通了，但C和D都没有和ABE中的任何一个连通，那么表会变成：
A 1
B 1
C 3
D 3
E 1
又过一些时候 C或D 的任意一个和 ABE中的任意一个连通了，则表会变成
A 1
B 1
C 1
D 1
E 1
一但表中所有点的编号全都统一了，就说明现在整张图就是连通的了。此时的时间就是所求的时间。


[ 本帖最后由 pangding 于 2011-4-26 10:24 编辑 ]

很好、很清晰的思路，可实施起来估计还是有点难度的

两个城镇连通应该是max(|x2-x1|,|y2-y1|)吧。

另一个思路。
对x坐标，y坐标分别升序排序，得到a,b序列，分别求相邻元素的差，得到c,d序列。
max(max(c1,c2,,,cn),max(d1,d2,,,dn))得出结果。在这个时间内所有城镇必定会连通。不过我不能证明其正确性。

哦，是 max ，之前写错了。

我形容的是助教的思路，其它方法肯定要先排序呀。

4楼 说的必定连通是对的。即可以肯定 4楼 给的表达式是一个时间的上界。

证明很容易：
设所有的点，按 x 坐标主序排序后，得到的排列为 a1, a2, ... , an
那么在上述时间 t 后，对 a 中任意两相邻点 a[i] 和 a[i+1]
由 t 的定义，易知它大于所有相邻元素的相应坐标的差，即有 t > x[i+1] - x[i] 且 t > |y[i] - y[i+1]|。
所以 ai 和 a[i+1] 肯定是连通的。由 i 的任意性，可以断言每两个相邻点都是连通的。所以整张图也是连通的。


但它应该不是我们要求的时间。因为可能存在比这小的时间满足连通性条件。
考虑两个点，x1 = (0, 0), x2=(4, 0) 这是一个已序的，
c, d 序列是 4 和 0。按 4楼的说法，求得的值是 t = 4。但其实2秒后这两个点就连通了。

哎，貌似说错了、、

[ 本帖最后由 玩出来的代码 于 2011-4-26 21:58 编辑 ]

对于类似x1=(0,0,),x2=(4,0)的点来说他们的连线与x轴或y轴平行，那么是否可以增加一个判断若x或y坐标上最大距离的点的连线与x或y轴平行，就result/2，与第二大元素比较，若result/2>max(2),那么result/=2; 否则result=max(2).重复判断、、

还是不一定对。

考虑
a1=(0,1) a2=(1,0) a3=(2,4)
它是按 x 主序排好的。
c, d 序列是
1, 1 和 1, 4
现在没有两个点是平行的，算出来应该是 4
但其实 3 秒后这三个点连通。


这个例子如果按 y 主序排列可以得到 3 这个答案。但事实上能举出按这两种方式排列都不对的例子。

不过你这个思想非常好，我昨天看到你的想法之前也没什么好的做法，但看了之后开阔了思路。研究了一会，虽然感觉不太对，但方向应该是对的。
你可以再想想，没准能想出来呢~~ 等我有空了我也考虑考虑。

哦，你说的是分别升序排列，不是主序排列。那恐怕都不是上界呀。就是和我 6楼 证的情况不一样。

那我刚才举的那个例子不行。现在也不清楚是不是对的，我有空也想想看吧。但没准都存在特殊的情况，使得达到这个时间后图都不连通。