给定n个点，如何找到给定距离的点的数量

Question

我有一个 n unique 点 (X,Y) 的输入，这些点在 0 到 2^32 之间（包括 0 和 2^32）。 坐标为整数。

我需要创建一个算法来查找距离为恰好 2018的对点的数量。

我想过检查所有其他点，但这将是O(n^2)，我必须提高它的效率。我还考虑过使用集合或向量，并根据与原点的距离使用比较器对其进行排序，但这根本没有帮助。

那么我怎样才能高效地做到这一点呢？

Answer 1

存在一个斜边为 2018 年的毕达哥拉斯三元组：1118²+1680²=2018²。

由于所有坐标都是整数，因此两点的坐标（X 和 Y）之间唯一可能的差异是 0、1118、1680 和 2018。

查找 X（或 Y）坐标之间具有给定差值的所有点对是一个简单的

n log n

操作。

2018 年以外的数字可能需要更多的工作，因为它们可能是多个毕达哥拉斯三元组的成员（例如 2015 年是 3 个三元组的斜边）。如果该数字不是作为常量给出，而是在运行时提供，则必须使用该斜边生成所有三元组。这可能需要一些

sqrt(N)

的努力（N 是斜边，而不是点数）。人们可以在数学堆栈交换上找到一个食谱，例如这里（还有很多其他的）。

Answer 2

您可以尝试使用四叉树。首先，您开始将点排序到四叉树中。您应该指定单元格大小的下限，例如2048 是 2 的幂。然后迭代这些点并计算到同一单元格中的点以及到相邻单元格中的点的距离。这样你应该能够大大减少距离计算的数量。

主要的困难可能是实现树结构。您还必须找到一种方法来查找相邻单元格（您必须包括在树中向上遍历的可能性）

在最好的情况下，这个复杂性可能是 O(n*log(n))，但不要让我局限于此。

关于距离计算的另一句话：如果你不这样做，你可能会更快

dx = p1x - p2x;
dy = p1y - p2y;
if ( sqrt(dx*dx + dy*dy) == 2018 ) {
    ...
}

但是

dx = p1x - p2x;
dy = p1y - p2y;
if ( dx*dx + dy*dy == 2018*2018 ) {
    ...
}

平方比求平方根更快。所以只需将距离的平方与 2018 年的平方进行比较即可。

Answer 3

如果 2018 年是 0 到 n 之间的任意点，我们该如何解决？