URI Online Judge | 1938

Rectangle Park

By Vinícius Fernandes dos Santos, Centro Federal de Educação Tecnológica de Minas Gerais Brazil

Timelimit: 1

Retangolândia is a very old city and therefore saves many historical riches. The city was planned several decades ago, with all its streets going in north-south or east-west directions. Currently, there is a revitalization project of the city, in which a new rectangular square will be made. The choice of the new square will be made by the government but for the moment they are interested in what are the possible positions for the square, taking into consideration that the square should be aligned with the streets and thus when viewed in a map, its sides should be horizontal and vertical segments. In order to reconcile the historical riches with the new initiatives, some precautions must be taken.

There light poles, of the XIX century throughout the city. For its historical value, no post can be overthrown. Because of the wear and tear and lack of maintenance, no street has more than one remaining post. For positioning the square, however, you do not want one of these poles is inside it. Moreover, the new square landscape design provides two historical poles are in two of the corners. The figure below shows an example with four poles and three possible locations for the square.

The city hall hired a georeference company to map the lampposts positions. With this data at hand, the next step is to determine how many possible locations exist for the park, so the size of the teams necessary to evaluate each location can be estimated.


The first line entry contains an integer N, 1 ≤ N ≤ 3000, representing about the number of poles. The following lines describe N, each of, the position of a pole. The position of a pole is given by a pair of integers X and Y, -108X, Y ≤ 108, corresponding to their coordinates in the plane.


Your program should produce a single line containing the number of different possible locations of the square.

Input Samples Output Samples


1 7

4 3

3 4

9 1



1 7

5 5

2 2

8 8

6 -1



1 1

2 2

-2 200

100 3

-6 -6

-51 19

-3 -1

8 -2