找到(x,y)坐标之间的最大距离

Question

我试图计算一个大的2D输入的最大曼哈顿距离,输入由(x,y)s组成,我想要做的是计算这些坐标之间的最大距离小于O(n ^ 2)时间,我可以通过遍历所有元素来做O(n ^ 2),例如:
*(两点(X1,Y1)和(X2,Y2)之间的曼哈顿距离是:| X1-X2 | + | Y1- Y2 |)

for ( 0 -> n )  
   for ( 0-> n )   
       { // here i calculate |Xi - Xj| + |Yi - Yj| which is maximum }  

但它不能有效地用于非常大的输入:(
任何人都有任何想法更好的算法？

Answer 1

如果我们只考虑这样的结果,那么只有两种情况需要考虑Xi <= Xj.

• 如果Yi <= Yj,那么距离是(Xj + Yj) - (Xi + Yi)
• 否则,距离是 (Xj - Yj) - (Xi - Yi)

通过将其分解为这些情况,我已经摆脱了绝对值函数,使得更容易推断距离.

因此,我们只需选择最小值和最大值x+y,然后计算距离.然后选择具有最小值和最大值的点x-y,并计算距离.这两个距离中的一个是你的最大距离.

这可以在O(n)渐近最优的情况下完成.

Answer 2

它非常简单,可以计算出来 O(n)

让我们x1>x2和y1>y2

max(|x1-x2|+|y1-y2|) = max(x1-x2+y1-y2) = max(x1+y1) - min(x2+y2)

让我们 x1>x2和y1<y2

max(|x1-x2|+|y1-y2|) = max(x1-x2-y1+y2) = max(x1-y1) - min(x2-y2)

现在用x2更改x1并获得相同的结果.

所以一般来说你的解决方案是

max ( (max(xi+yi)-min(xi+yi)), (max(xi-yi) - min(xi-yi)) )