Square Pasture#10372
Farmer John's largest pasture can be regarded as a large 2D grid of square "cells" (imagine a huge chessboard). Currently, there are cows occupying some of these cells.
Farmer John wants to build a fence that will enclose a square region of cells. The square must be oriented so its sides are parallel to the and axes, and it can be as small as a single cell. Please help him count the number of distinct subsets of cows that he can enclose in such a region. Note that the empty subset should be counted as one of these.
The first line contains a single integer (1 \leq n \leq 200).
Each of the next lines contains two integers, indicating the coordinates of a cow's cell. All coordinates are distinct from each other, and all coordinates are distinct from each other. All and values lie in the range 0 \ldots 10^9.
Note that although the coordinates of cells with cows are nonnegative, the square fenced area might possibly extend into cells with negative coordinates.
Print the number of subsets of cows that Farmer John can fence off. It can be shown that this quantity fits within a signed -bit integer.
In this example, there are subsets in total. Farmer John cannot create a fence enclosing only cows and , or only cows and , so the answer is 24-2=22.
Example 1
Example 2