问题求助之修建公路

助教的意思就是让时间从小往大变：比如看看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))得出结果。在这个时间内所有城镇必定会连通。不过我不能证明其正确性。

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秒后这两个点就连通了。

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

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

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

如果是这样的话，万一某两个城镇通过第三个城镇连接3会更短的话，程序会不会出问题？？

恩是搞错了，应该改用求|X1-X2|,|Y1-Y2|的较大值...

顶上去 等代码

玩出来的代码：考虑四个点，
a1=(-2,-1), a2=(-1,-2), a3=(1,2), a4=(2,1)
x 排序 -2 -1 1 2
y 排序也是 -2 -1 1 2
差序列都是 1 2 1
按你的说法 2 秒后连通。但其实这四个点连通需要 3 秒。

突然发现忽略了一点，如果两个镇在同一Y轴或X轴
像（2，3）（2，-1）那么联通时间就应该为（3-（-1））/2=2