UOJ Logo LFYZ Online Judge

LFYZOJ

#350. 【2018 国庆雅礼 NOIP 培训】D6T3 Rectangle

统计

问题描述

平面上有 $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 培训。一切权利归原作者所有。侵权删除。