Rectangle

rectangle.cpp/in/out

• 时间限制：2.0s
• 空间限制：512MB

题目描述

平面上有 $n$ 个点，第 $i$ 个点的坐标为 $X_i, Y_i$。对于其中的一个非空点集 $S$，定义 $f(S)$ 为一个最小矩形，满足：

• 覆盖 $S$ 中所有的点（在边界上也算覆盖）；
• 边与坐标轴平行。

求所有不同的 $f(S)$ 的面积和对 $10^9 + 7$ 取模的结果。两个矩形被认为是不同的，当且仅当它们顶点坐标不同。

输入格式

从文件 rectangle.in 中读入数据。

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $X_i, Y_i$。

输出格式

输出到文件 rectangle.out 中。

一行一个整数表示答案。

样例 1 输入

4
1 2
3 1
4 4
5 1

样例 1 输出

45

样例 1 解释

有 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)$。

样例 2

见选手目录下的 rectangle/rectangle2.in 与 rectangle/rectangle2.ans。

样例 3

见选手目录下的 rectangle/rectangle3.in 与 rectangle/rectangle3.ans。

数据范围

对于所有数据，满足 $2 \le n \le 10^4$，$1 \le X_i, Y_i \le 2500$，没有重复的点。

• Subtask 1 (13%)：$n \le 18$。
• Subtask 2 (9%)：$n \le 50$。
• Subtask 3 (25%)：$n \le 300$。
• Subtask 4 (21%)：$n \le 2500$，$X_i \neq X_j$，$Y_i \neq Y_j$。
• Subtask 5 (19%)：$n \le 2500$。
• Subtask 6 (13%)：没有特殊的约束。