Rectangular Pasture

题目描述

农夫约翰最大的牧场可以看作一个由方形“格子单元”组成的巨大二维网格（可以想象成一个巨大的棋盘）。目前，有 $N$ 头奶牛占据了其中一些格子（$1 \leq N \leq 2500$）。 农夫约翰想建造一段围栏，将一个由格子组成的矩形区域围起来；该矩形必须与 $x$ 轴和 $y$ 轴平行，并且它可以小到只有一个格子。请你帮助他统计：他能用这样的矩形区域围住的奶牛子集一共有多少种不同的可能。注意，空集也应当计为一种。

输入格式

第一行包含一个整数 $N$。 接下来 $N$ 行每行包含两个用空格分隔的整数，表示一头奶牛所在格子的坐标 $(x,y)$。所有的 $x$ 坐标两两不同，所有的 $y$ 坐标也两两不同。所有 $x$ 和 $y$ 的取值都在范围 $0 \ldots 10^9$ 内。

输出格式

输出农夫约翰能够围起来的奶牛子集数量。可以证明该数量可以用有符号 64 位整数表示（例如 C/C++ 中的 long long）。

4
0 2
1 0
2 3
3 5

13

提示

一共有 $2^4$ 个子集。农夫约翰无法建造围栏使其恰好只围住奶牛 1、2、4，或只围住奶牛 2、4，或只围住奶牛 1、4，因此答案为 $2^4-3=16-3=13$。 SCORING: 测试点 2-3 满足 $N\le 20$。 测试点 4-6 满足 $N\le 100$。 测试点 7-12 满足 $N\le 500$。 测试点 13-20 没有额外限制。 Problem credits: Benjamin Qi

标签: USACO|2020|Silver

来源

USACO|2020|Silver