Find a unique pair of pairs

Question

Given a set of n pairs of integers, is there a fast way to determine if there exists two pairs (x_1,y_1) and (x_2, y_2) in the set such that x_1 != x_2 and y_1 != y_2?

For example, {(0,1), (0,2), (2,1), (3,2)} has {(0,2), (2,1)}. However {(1,0), (2,0), (3,0) does not have any satisfying pair of pairs.

A naive approach just tries all pairs of pairs. There are O(n^2) of these. Can you get something closer to linear time?

---

If it speeds things up we can assume the pairs are stored as pointers from an array in sorted order (by then first then second coordinate).

Answer 1

You can use following O(n) algorithm. To simplify the notation let me call (x,y) a point.

Note that such pair of points does not exist only when all points lay on one line parallel to the axis. Determine this line by first two points and then, for each new point, check if it lays on the same line or not.

Answer 2

If the first two pairs are (x1, y1) and (x1, y2) [y1 != y2], then from the remaining list of pairs, if you find any x != x1, its corresponding y shall either not be equal to y1 or not equal to y2.