笛卡尔平面中的点对之间的距离

Question

我最近在Foursquare的采访中被问到以下问题.我无法对此进行编码.

我们给出N个点(xi,yi),其中1 <= i <= N,并且两个数字a和b,使得两个点(x1,y1)和(x2,y2)之间的距离是max(a*| x1) -x2 |,b*| y1-y2 |),我们如何计算每对点之间的距离之和？

点数N是高数.

任何人都可以帮忙解决这个问题吗？请解释算法,除了遍历所有点对的蛮力.

Answer 1

首先重新调整轴,以摆脱a和b因素.定义x' = a * x, y' = b * y'.然后距离是:

max(a*|x1-x2|,b*|y1-y2|) =
max(|a*x1-a*x2|,|b*y1-b*y2|) =
max(|x'1-x'2|,|y'1-y'2|)

其次,将坐标系旋转45度,将其更改为Taxicab几何.定义s = (x' + y')/2, t = (x' - y')/2.然后我们有x' = s + t, y' = s - t.

然后我们可以再次重写距离的定义:

max(|x'1-x'2|,|y'1-y'2|) =
max(|s1 + t1 - s2 - t2|,|s1 - t1 - s2 + t2|) =
max(|(s1 - s2) + (t1 - t2)|,|(s1 - s2) - (t1 - t2)|) =
|s1 - s2| + |t1 - t2|
-- last equation comes from the fact that max(|a + b|, |a - b|) = |a| + |b|

通过这个定义,我们可以分别沿s轴线和沿t轴分别对距离求和并添加结果.

解决这个问题的一维版本非常简单.您可以沿轴对点进行排序.然后,在(基于0的)i第 - 和i+1第 - 点之间的每个段将贡献(i + 1) * (N - i - 1) * distance.足以将这些值相加.

整体解决方案需要O(n lg n),因为它需要对点进行两次排序.