algorithm - 在 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(NlogN) 解决方案可能使用类似快速排序的分区:

像这样制作比较函数:

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

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

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