问题求助之修建公路
★实验任务在二维坐标系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)应该都行。
没看明白,求各位大侠帮帮忙,理下思路……