Question: I am trying to solve an algorithm problem. I have 2 arrays, say A and B, containing some points. Length of A and B are the same. I know that all points in A and B are distinct. Now, I want to find all the pairs with the same distance to a line. There is also one more rule. I cannot compare 2 points both in A and both in B.

How can I solve this problem in O(nlogn)? I think this is a divide and conquer problem, but I could not find a solution.

Thanks in advance. 

EDIT: An example:

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

```

EDIT2: Assume that all distances are also distinct.

Answer: 
This is esoteric *(prohibition of comparing two points looks silly here)* variant of **nuts and bolts** problem. O(NlogN) solution might use quicksort-like partition:

Make comparison function like this:

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

```

Choose random index `a_idx` from A. Partition B array using Compare with `a_idx`. Resulting pivot `B[b_idx]` corresponds to `A[a_idx]` element. Now partition array A against `b_idx`. You have a pair of equal elements and left and right subarrays of points with smaller and larger distances.

Repeat for both halves of arrays until all points are paired.
A hash table (`std::unordered_map`) which was keyed on the distance, would have a feature of N insertions of order O(1). However, if there was a collision with the key it would break the constraint of comparing 2 A elements.

Searching the hash table for elements in B would also be O(1). So the performance would be O(N) - but I can't see how to avoid the collision case.