Try some kind of "divide and conquer" algorithm.
My algorithm is based on the algorithm of finding the closest pair of points, used the same pruning.
Believe me, what you think is impossible this time it's possible.