3527. [USACO20Dec Gold]Square Pasture

【题目描述】

Farmer John 最大的牧草地可以被看作是一个由方格组成的巨大的二维方阵（想象一个巨大的棋盘）。现在，有 $N$ 头奶牛正占据某些方格（$1 \leq N \leq 200$）。

Farmer John 想要建造一个可以包围一块正方形区域的栅栏；这个正方形必须四边与 $x$ 轴和 $y$ 轴平行，最少包含一个方格。请帮助他求出他可以包围在这样的区域内的不同的奶牛子集的数量。注意空集应当被计算为答案之一。

【输入格式】

输入的第一行包含一个整数 $N$。以下 $N$ 行每行包含两个空格分隔的整数，表示一头奶牛所在方格的坐标 $(x,y)$。所有 $x$ 坐标各不相同，所有 $y$ 坐标各不相同。所有 $x$ 与 $y$ 的值均在 $0 \ldots 10^9$ 范围内。

【输出格式】

输出 FJ 可以包围的奶牛的子集数量。可以证明这个数量可以用 32 位有符号整数型存储。

【样例输入1】

4
0 2
2 3
3 1
1 0

【样例输出1】

14

【样例输入2】

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

【样例输出2】

6

【样例说明】

在第一个样例中，共有 $2^4$ 个子集。FJ 不能建造一个栅栏仅包围奶牛 1、3，或仅包围奶牛 2、4，所以答案为 $2^4-2=16-2=14$。

【数据规模与约定】

对于$ 25\% $的测试数据(测试点$ 1\sim5 $)，所有奶牛所在的方格的坐标均小于 $ 20 $。

另有$ 50\% $的测试数据(测试点$ 1\sim10 $)，满足 $ N \le 20 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 十二月月赛 Gold 组