Consider n distinct points on a plane.
Two points from that set are said to be friends, when there exists a rectangle with sides parallel to coordinate axes that contains those two points and doesn't contain any other point from the given set. A rectangle is said to contain a point if the point lies within the rectangle or on its border.
How many pairs of friends are there among the given points?
The input consists of multiple sets of testdata and is terminated by EOF. Each set of input is described as follow:
The first line of the input file contains an integer n, 1<=n<=100000.
The next n lines contain two integers each, the coordinates of the given points. The coordinates don't exceed 109 by absolute value.
Output one integer number for each testcase on a single line — the sought number of pairs of friends.
5 0 0 0 2 2 0 2 2 1 1 1 0 0
8 0
Migrated from old NTUJ.
sgu512
| No. | Testdata Range | Score |
|---|