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

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 1

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.