我觉得应该这样理解...
输入示例
2 （城镇数量）
0 0 （第一个城镇的坐标）
5 5  （第二城镇的坐标）
输出示例
5 （两城镇间联通所需时间，可以用公式:（|X1-X2|+|Y1-Y2|)/2求出来...
如果城镇数是3以上的话，就需要把每两个城镇联通时间算出来，然后求最大值...

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

首先这个公式 （|X1-X2|+|Y1-Y2|)/2 就不对
上面都说过了是 max(.....).

你想下，(0, 0) 和 (1, 3) 显然是3秒后连通嘛。要按你的公式是2秒，那会根本没连上。

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

按照x,y分别排序，求差，求最大值,最长距离的两点连线与坐标轴不平行时，他是一个时间上限的，这个值是连通的最大值了，加上对于坐标轴平行的判断最终求得的结果也是一个上限。需要证明的就是这个上限也是它的下限、

假设最后求出的两点为(xi,yi),(xj,yj),最大距离为xj-xi,那么在(xi,xj)之间必定不会存在序列中的点，在xi左边与xj右边的城镇连通的最短时间也就是xi,与xj连通的时间了。对于y轴是一样的。这是否对呢。不知道是否严谨、pangding数学在行。看看能否用更严谨的数学证明来证明它的正确性。

顶上去 等代码

输入示例
2
0 0
5 5
输出示例
5

那个点在修路 不是两个点都修嘛？  

玩出来的代码：考虑四个点，
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 秒。

现在这道题我只有 O(n^2) 级的算法。而且我明显感觉不是最好算法。

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