这类问题都有一个朴素的O(n^2)的算法，下面重点讨论更加高效的算法。

1. 最远曼哈顿距离

即在N个点中求两点i和j使得|xi-xj|+|yi-yj|的值最大。

设距离最远的两点为i,j，可知所求的最大距离必定有(xi-xj)+(yi-yj), (xj-xi)+(yi-yj), (xi-xj)+(yj-yi), (xj-xi)+(yj-yi) 四种形式之一，变形一下即(xi+yi)-(xj+yj), (-xi+yi)-(-xj+yj), (xi-yi)-(xj-yj), (-xi-yi)-(-xj-yj)。于是只要对所有的点(xi,yi)，依次计算出(xi+yi),(xi-yi),(-xi+yi),(-xi-yi)这四种形式，分别对这四种形式的序列求最大值与最小值的差即为四种形式的最大距离，四个距离的最大者即为最后所求。

换一个角度来理解就是：如果把问题降到一维，那么结果显然就是取最大值与最小值之差。现在我们实际上是枚举了四个方向，把二维的点分别映射到上面求解。

容易扩展到多维空间的情况。时间复杂度为O(n*(2^k))，其中k为维数。

例题: POJ2926 Requirements

2. 最近欧几里得距离

即求两点i和j使得sqrt((xi-xj)*(xi-xj)+(yi-yj)*(yi-yj))最小。

这个问题是分治法的经典应用，在任何一本算法书上应该都可以找到（虽然我认为这个算法并不太优美，要是真写起来也很恶心 = =b）复杂度O(nlogn)。

3. 最长欧几里得距离

这个……似乎没有什么太好的办法。印象中是一次区域赛的网上预赛的题目，貌似说过的人都是卡过去的。一个比较好的常数级优化是先对点集求凸包，易知要求的点一定在凸包上，因此只需枚举凸包上的点即可。对于随机数据这个优化应该是相当有效的。

(10.5补记: 这个有O(nlogn)+O(n)的算法,找到了一些介绍这个的地方http://cgm.cs.mcgill.ca/~orm/rotcal.html,不过还没看懂 = =b)
(非常感谢st同学 ^_^)

Trace back:http://roba.yculblog.com/