After some failed attempts with O(n)=n*n/2, finally I found an O(n)=n solution.
In plain C, it took 0.09s and 1.5Mb. (just from curiosity tried the same with C# - 14MB used RAM :))

The arrays of X and Y coordinates can be sorted independently from each other.

So basically, this input:
3
1 3
2 1
3 2
will have exactly the same result (which is 2) as
3
1 1
2 2
3 3

can you proof it?

Assuming a (x1, y1), b (x2, y2), then the distance from c (x3, y3) to (x1, y1) and (x2, y2) is equivalent to the distance from (x1, y2) and (x2, y1)