Enclosed Cow Subsets

Farmer John has a huge field which can be thought of as a 2D grid. There are \(N\) cows (with \(1\le N\le200\)) each occupying a distinct grid cell. Farmer John wants to build a fence in the shape of an axis‐aligned square (i.e. its sides are parallel to the \(x\) and \(y\) axes) so that the fenced area exactly contains a subset of cows. In other words, if you list all cows inside the square, you obtain some cow subset \(S\); different square placements may yield the same subset, but they are counted only once. Note that the square must contain at least one grid cell and the empty subset (obtained by choosing a square that contains no cow) is also considered.

More formally, given the locations \((x_i,y_i)\) of the \(N\) cows this problem asks you to compute how many distinct subsets \(S\) of cows exist for which there exists an axis‐aligned square \(Q\) with side length \(L\) (for some positive integer \(L\)) such that:

[ S = {; i ; : ; x_0 \le x_i \le x_0+L-1 ; \text{and}; y_0 \le y_i \le y_0+L-1 }, , ]

for some integers \(x_0, y_0\). You are to include the empty set as one valid answer.

Note: A crucial observation is that if a square fence encloses a nonempty subset \(S\), then if we define \( x_{\min}=\min_{i\in S}x_i,\quad x_{\max}=\max_{i\in S}x_i,\quad y_{\min}=\min_{i\in S}y_i,\quad y_{\max}=\max_{i\in S}y_i, \) any square that contains \(S\) must cover at least the rectangle \[ [x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}], \]

and its side length will be at least (L=\max(x_{\max}-x_{\min}+1,; y_{\max}-y_{\min}+1)). By sliding the square appropriately (so that one of its boundaries coincides with a cow coordinate) one can always assume the left and bottom boundaries come from the set of cow (x) and (y) coordinates. This observation allows an (O(N^3)) solution given that (N\le200>.

inputFormat

The first line contains a single integer \(N\) (\(1\le N\le200\)). Each of the next \(N\) lines contains two integers \(x_i\) and \(y_i\) representing the coordinate (column and row) of a cow. All cow positions are distinct.

outputFormat

Output a single integer: the number of distinct cow subsets (including the empty set) that can be exactly enclosed by an axis‐aligned square fence.

sample

3
0 0
0 1
0 2

7