在 O(nlogn) 中找到与一条线距离相同的所有点对

Question

我正在尝试解决算法问题。我有 2 个数组，比如 A 和 B，其中包含一些点。 A和B的长度相同。我知道 A 和 B 中的所有点都是不同的。现在，我想找到与一条线距离相同的所有线对。还有一个规则。我无法同时比较 A 和 B 中的 2 个点。

如何在 O(nlogn) 中解决这个问题？我认为这是一个分而治之的问题，但我找不到解决方案。

提前致谢。

编辑：一个例子：

Line -> y=0
A = {(1,2), (3,4)}
B = {(1,-2), (3,-4)}
Output -> {{(1,2), (1,-2)}, {(3,4), (3,-4)}}

EDIT2：假设所有距离也不同。

Answer 1

为什么不是 O(n) 例程？哈希从 A 中的每个点到直线的距离：

Distance 1 -> {A[0]}
Distance 2 -> {A[1]}

遍历 B，如果从 B[i] 到 Line 的距离已经被散列，添加 B[i] 以形成一对：

Distance 1 -> {A[0], B[0]}
Distance 2 -> {A[1], B[1]}

Answer 2

以距离为关键字的哈希 table (std::unordered_map) 将具有 O(1) 次序的 N 次插入的特征。但是，如果与键发生冲突，它将打破比较 2 个 A 元素的约束。

在散列 table 中搜索 B 中的元素也是 O(1)。所以性能将是 O(N) - 但我看不出如何避免碰撞情况。

Answer 3

这是深奥的（禁止比较两点在这里看起来很傻） 具体细节 问题的变体。 O(NlogN) 解决方案可能使用类似快速排序的分区：

像这样制作比较函数：

float Compare(int A_Index, int B_Index)
   return Distance(line, A[A_Index]) - Distance(line, B[B_Index])

从 A 中选择随机索引 a_idx。使用 Compare with a_idx 分区 B 数组。生成的枢轴 B[b_idx] 对应于 A[a_idx] 元素。现在根据 b_idx 对数组 A 进行分区。你有一对相等的元素和距离越来越小的点的左右子数组。

重复数组的两半，直到所有点都配对。

Finding all pair of points with the same distance to a line in O(nlogn)