Hide

Problem C
Treehouse

/problems/lthchallenge22.treehouse/file/statement/en/img-0001.jpg
Pusheen outside a treehouse. Photo: Måns Magnusson. CC0
Pusheen wants to build a treehouse in the Treehouse forest in Brunnshög in the north of Lund. The treehouse should to be built on a square platform in the treetops, with a tree in each of the four corners. When Pusheen has picked a spot to built the treehouse, trees that are located between the corners will be cut down. Pusheen has a 2D map with all the (x, y)-coordinates of the trees in the forest. In how many places can they build a square treehouse?

Input

The first line has an integer $4 \leq N \leq 2\, 000 $, the number of trees in the forest. Each of the following $N$ lines has two integers $-10,000\leq x_ i, y_ i \leq 10,000$, the x- and y-coordinates of tree $i$. All points are distinct.

Output

An integer, the number of suitable spots for a tree house.

Scoring

Group

Points

Limits

$1$

$20$

$N \leq 50$

$2$

$80$

No further restrictions

Sample Explanation

\includegraphics[width=0.3\textwidth ]{./img/sample1.png}
Illustration of the two possible treehouse locations in sample 1.

Sample Input 1 Sample Output 1
9
1 5
1 7
3 1
3 5
3 7
5 7
6 2
7 3
7 6
2

Please log in to submit a solution to this problem

Log in