[USACO20DEC] Square Pasture G

题目描述

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

输入输出格式

输入格式


输入的第一行包含一个整数 $N$。以下 $N$ 行每行包含两个空格分隔的整数,表示一头奶牛所在方格的坐标 $(x,y)$。所有 $x$ 坐标各不相同,所有 $y$ 坐标各不相同。所有 $x$ 与 $y$ 的值均在 $0…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

420

说明

- 测试点 1-5 中,所有奶牛所在的方格的坐标均小于 20 。 - 测试点 6-10 中,$N≤20$。 - 测试点 11-20 没有额外限制。 供题:Benjamin Qi