Given the constraints of this problem (n <= 1E6), how can we solve this problem?

The naive brute force solution( O(n^2) ) checking all pairwise distances will fail. Any ideas will be appreciated.