P6905: 矩形牧场

---

【题目描述】

【题目描述】
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 没有额外限制。
 
 

题目类型~

USACO-2020-银-12月 

咻咻~

提交答案 状态 返回