I know the O(n^2) solution to the problem. It tries to make a rectangle for every pair of points. This approach times out for subtask 2 which needs an O(n) or O(n.logn) solution.

So what is the O(n) approach for this problem?

In case you are interested, my O(n^2) solution is here : Ideone

I think that a sliding window like approach could work here. Hints are also appreciated.