← 返回题目列表

AtCoder · tenka1_2015_final_e

E. 天下一杯

中文机器翻译题面 查看原题

問題文

N 矩形。 第 i 个矩形的宽度为 高度是 w_i 以任意顺序排列 h_i 。

N 矩形,制作一个杯子。 此时,不要旋转每个矩形,而是要确保所有矩形的底边都在一条直线上。 另外,请确保相邻的矩形彼此完全接触。

图 1:杯子示例

想象一下在玻璃杯中装满水。 此时的坐标 P 中水存在的充分必要条件如下。

  • P 不在任何矩形内。 当从
  • P 向左和向右绘制半线时,两条半线与其中一个矩形有公共点。

当玻璃杯装满水时,水的总面积为 它被称为 容積 。

图 2:装满水的玻璃杯示例(第 71 卷)

如何通过排列矩形来制作杯子 N! 没错。那些 N! 街上眼镜的体积总和 10^9+7 求余数。


入力

输入是按以下格式从标准输入给出的。

N
w_1 h_1
w_2 h_2
:
w_N h_N
  • 1 行包含一个表示矩形数量的整数。 一个整数,表示第 N (3≦N≦10^5)。
  • 2 从线 N 行 i 行中,i 个矩形的宽度和高度 打印除以 w_i,h_i (1≦w_i,h_i≦10^9) 用空格分隔。 在

部分点

针对此问题设置了部分分数。

  • 3≦N≦8 的数据集 给出 15 点。
  • 3≦N≦2,000 的数据集,则进一步 给出 55 点。
  • 3≦N≦10^5 的数据集,则进一步 给出 70 点。总共 140 点。

出力

N! 街上眼镜的体积总和 10^9+7 后的余数。 在输出末尾添加换行符。


入力例1

3
1 4
1 5
4 1

出力例1

24

6 街道上眼镜的体积总和为 24 。


入力例2

4
1 1
1 2
1 2
1 2

出力例2

12

宽度和高度相同的矩形也分开排列。


入力例3

8
2 5
1 7
4 2
1 10
3 4
2 6
5 1
3 8

出力例3

1881888