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

Question

我有n 个 唯一点 (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 是斜边，而不是点数）。人们可以在数学堆栈交换上找到一个食谱，例如这里（还有很多其他的）。