笛卡尔平面上两点间的距离

Question

最近在Foursquare面试中，我被问到了以下问题，但我无法编写代码。

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

点的数量N很大。

请问有人知道如何解决这个问题吗？请解释算法，除了暴力遍历所有点对的方法。

- user12457112

---

这是暴力算法。我要寻找更好的算法。显然，我可以想到那个。 - user12457112

他们要求最佳优化算法，而不是暴力破解。 - user12457112

@rayryeng 是的，我提到了。我的错。抱歉。 - user12457112

这是一个编程问题，我被要求编写代码。我认为这是合适的地方。 - user12457112

也许有一些聪明的鞋带公式？ - biziclop

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度，变成出租车几何。定义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-based）i个和i + 1个点之间的每个线段都会贡献(i + 1) * (N - i - 1) * distance。只需对这些值进行求和即可。

总体解决方案需要O(n lg n)，因为它需要两次对点进行排序。

- zch

---

我不理解你对于一维问题的解决方案。你是采用i：[0..n-1]还是[1..n]？我无法理解任何一种方式。取3个点（1,0），（2,0），（3,0），A=1，B=0：总距离应该为4。根据你的公式：当i=[1..3]时，1*(3-1-1)*1+2*(3-2-1)*1 = 1 或者当i=[0..2]时，0*(3-0-1)*1+1*(3-1-1)*1 = 1。 - Wouter

很棒的解决方案，已点赞！但我想在这里学到一些东西。关键是替换s和t的部分。你是怎么想出s=(x+y)/2和t=(x-y)/2这个替代方法的？在几何问题中常见吗？<br>还有，它与出租车几何和将坐标轴旋转45度有什么关系呢？因为那样的话，新的点会变成其他什么样子呢？（应用公式s = xcosQ - ysinQ, t = xsinQ+ycosQ） - Nikunj Banka

@Wouter，我修正了公式，之前错了一个。在该线段左侧有i + 1个点，在右侧有N - i - 1个点，因此包含该线段的点对数为(i + 1) * (N - i - 1)。 - zch

@NikunjBanka ，如果您从某个点开始画距离为1的点，你会得到最大度量下的正方形和曼哈顿度量下的菱形，所以我知道我可以通过旋转将一个转换为另一个。幸运的是，sin 45 = cos 45 ，因此我不关心保留比例，所以我使用1/2只是因为它使方程式更容易。 - zch

Answer 2

我们想要计算。

sum_i sum_j max(a |xi - xj|, b |yi - yj|).

通过映射 xi' = a xi 和 yi' = b yi 进行简化问题，并计算

sum_i sum_j max(|xi' - xj'|, |yi' - yj'|).

简化问题，通过映射 ui = (xi + yi)/2 和 vi = (xi - yi)/2 并计算。

sum_i sum_j (|ui - uj| + |vi - vj|)
    = sum_i sum_j |ui - uj| + sum_i sum_j |vi - vj|.

为了在O(n log n)的时间内解决第一个子问题，以下是一些Python代码。

def one_d(us):
    us = sorted(us)
    return sum((2 * i - (len(us) - 1)) * u for (i, u) in enumerate(us))

- David Eisenstat