## Problem E. Empty rectangles ≡

• problems
• en ru
 Author: A. Baranov Time limit: 1 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

### Statement

Consider a set of N two-dimensional points represented by their coordinates (Xi, Yi).

It is required to determine the number of all possible rectangles that satisfy the following conditions:

• the vertices of the rectangle must belong to the original set of points,
and its sides must be parallel to the coordinate axes;
• among the remaining points, none should lie on the border or inside such a rectangle;
• the rectangle must be non-degenerate (have a non-zero area).

### Input format

Input starts with integer N,
followed by 2 × N integers, representing point coordinates: Xi, Yi.

### Output format

The output should contain
the number of detected rectangles.

### Constraints

All input points are different.

− 106 ≤ (Xi, Yi) ≤ 106,

4 ≤ N ≤ 105

### Sample tests

No. Standard input Standard output
1
12
-35 -17
43  10
24 -17
-16 -29
43  54
-35  40
43 -29
24  10
-16  54
-35  10
43 -17
24  40

3

2
12
-20 -34
17  34
-20  40
-10 -20
-43 -17
19  15
-15  16
0 -34
-32  19
0 -12
-13   0
0  40

0


0.075s 0.009s 13