Square Pasture

题目描述

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

输入格式

第一行包含一个整数 $N$。 接下来的 $N$ 行，每行包含两个用空格分隔的整数，表示一头奶牛所在格子的 $(x,y)$ 坐标。所有的 $x$ 坐标两两不同，所有的 $y$ 坐标两两不同。所有 $x$ 和 $y$ 的取值都在范围 $0 \ldots 10^9$ 内。 注意：虽然有奶牛的格子坐标都是非负的，但被栅栏围住的正方形区域可能会延伸到坐标为负的格子中。

输出格式

输出农夫约翰能够围起来的奶牛子集数量。可以证明该数量在有符号 32 位整数范围内。

4
0 2
2 3
3 1
1 0

14

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

420

提示

在这个例子中，总共有 $2^4$ 个子集。农夫约翰无法创建一个栅栏只围住奶牛 1 和 3，或只围住奶牛 2 和 4，因此答案是 $2^4-2=16-2=14$。 SCORING: 在测试点 1-5 中，所有包含奶牛的格子坐标都小于 $20$。 在测试点 6-10 中，$N\le 20$。 在测试点 11-20 中，没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2020|Gold

来源

USACO|2020|Gold