E - 天下一コップ
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 個の長方形がある。 i 番目の長方形は幅が w_i で高さが h_i である。
N 個の長方形を好きな順序で並べてコップを作る。 このとき、それぞれの長方形は回転させずに、すべての長方形の底辺が一直線上にあるようにする。 また、隣り合う長方形同士がちょうど接するようにする。
コップを水で満杯にすることを考える。 このとき、座標 P に水が存在するための必要十分条件は以下である。
- P はどの長方形の内部にもない。
- P から左および右向きへ半直線を引いたとき、どちらの半直線もいずれかの長方形と共有点を持つ。
コップを水で満杯にしたとき、水が存在する領域の総面積を 容積 と呼ぶ。
長方形を並べてコップを作る作り方は全部で 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