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

Question

我输入了 n unique 点 (X,Y)，它们在 0 到 2^32 之间（含）。 坐标为整数。

我需要创建一个算法来查找 对点的数量正好 2018.

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

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

Answer 1

您可以尝试使用 Quadtree。首先，您开始将您的点排序到四叉树中。您应该为单元格大小指定一个下限，例如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 2

有一个带2018斜边的毕达哥拉斯三元组：1118²+1680²=2018².

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

查找 X（或 Y）坐标之间具有给定差异的所有点对是一个简单的 n log n 操作。

2018 以外的数字可能需要更多的工作，因为它们可能是不止一个毕达哥拉斯三元组的成员（例如 2015 是 3 个三元组的斜边）。如果数字不是作为常量给出，而是在运行时提供，则必须生成所有带有此斜边的三元组。这可能需要一些 sqrt(N) 的努力（N 是斜边，而不是点数）。人们可以在 math stackexchange 上找到一份食谱，例如here（还有很多）

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

Given n points, how can I find the number of points with given distance

c++

sorting

algorithm

distance

coordinates