问题描述
平面上有 $n$ 个点，第 $i$ 个点的坐标为 $(X_i, Y_i)$。对于其中的一个非空点集 $S$，定义 $f(S)$ 为一个最小矩形，满足：
- 覆盖 $S$ 中所有的点(在边界上也算覆盖);
- 边与坐标轴平行。
求所有不同的 $f(S)$ 的面积和对 $10^9 + 7$ 取模的结果。两个矩形被认为是不同的，当且仅当它们顶点坐标不同。
输入格式
第一行一个整数 $n$。
接下来 $n$ 行，每行两个整数 $X_i, Y_i$。
输出格式
一行一个整数表示答案。
样例
Input
4 1 2 3 1 4 4 5 1
Output
45
Explanation
有 8 个面积大于 0 的不同矩形，以下是它们左下角和右上角的坐标：
(1, 1) ,(3, 2) ; (1, 1) ,(4, 4) ; (1, 1) ,(5, 2); (1, 1) ,(5, 4)
(1, 2) ,(4, 4) ; (3, 1) ,(4, 4) ; (3, 1) ,(5, 4); (4, 1) ,(5, 4)
3.7 Subtasks
对于所有数据，满足 $2 \le n \le 10^4 , 1 \le X_i, Y_i \le 2500$，没有重复的点。
- Subtask1(13%), $n \le 18$.
- Subtask2(9%), $n \le 50$.
- Subtask3(25%), $n \le 300$.
- Subtask4(21%), $n \le 2500, X_i \not = X_j , Y_i \not = Y_j$ .
- Subtask5(19%), $n \le 2500$.
- Subtask6(13%), 没有特殊的约束。
时间限制： $2\mathrm{s}$
内存限制： $512\mathrm{MB}$
来源
2018 国庆雅礼 NOIP 培训。一切权利归原作者所有。侵权删除。
