Problem Description

Farmer John's largest pasture can be seen as a huge 2D square grid made of cells (imagine a giant chessboard). Now, there are $N$ cows occupying some cells ($1 \le N \le 200$).

Farmer John wants to build a fence that encloses a square region. This square must have its sides parallel to the $x$-axis and the $y$-axis, and it must contain at least one cell. Please help him find the number of different subsets of cows that he can enclose in such a region. Note that the empty set should also be counted as one of the answers.

Input Format

The first line contains an integer $N$. The next $N$ lines each contain two space-separated integers, describing the coordinates $(x, y)$ of the cell occupied by a cow. All $x$-coordinates are distinct, and all $y$-coordinates are distinct. All values of $x$ and $y$ are in the range $0 \ldots 10^9$.

Note that although all cow cell coordinates are non-negative, the enclosed square region may include cells with negative coordinates.

Output Format

Output the number of subsets of cows that FJ can enclose. It can be proven that this number fits in a 32-bit signed integer type.

4
0 2
2 3
3 1
1 0

14

16
17 4
16 13
0 15
1 19
7 11
3 17
6 16
18 9
15 6
11 7
10 8
2 1
12 0
5 18
14 5
13 2

420

Hint

• In test cases 1 to 5, all cow cell coordinates are less than 20.
• In test cases 6 to 10, $N \le 20$.
• In test cases 11 to 20, there are no additional constraints.

Problem proposed by: Benjamin Qi.

Translated by ChatGPT 5