[USACO20DEC] Rectangular Pasture S

Farmer John 最大的牧草地可以被看作是一个由方格组成的巨大的二维方阵（想象一个巨大的棋盘）。现在，有 $N$ 头奶牛正占据某些方格（$1≤N≤2500$）。 Farmer John 想要建造一个可以包围一块矩形区域的栅栏；这个矩形必须四边与 $x$ 轴和 $y$ 轴平行，最少包含一个方格。请帮助他求出他可以包围在这样的区域内的不同的奶牛子集的数量。注意空集应当被计算为答案之一。

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

输出 FJ 可以包围的奶牛的子集数量。可以证明这个数量可以用 64 位有符号整数型存储（例如 C/C++ 中的long long）。

4
0 2
1 0
2 3
3 5

13

共有 $2^4$ 个子集。FJ 不能建造一个栅栏仅包围奶牛 $1$、$2$、$4$，或仅包围奶牛 $2$、$4$，或仅包围奶牛 $1$、$4$，所以答案为 $2^4-3=16-3=13$。 - 测试点 2-3 满足 $N≤20$。 - 测试点 4-6 满足 $N≤100$。 - 测试点 7-12 满足 $N≤500$。 - 测试点 13-20 没有额外限制。 供题：Benjamin Qi