← 返回题目列表

Codeforces · 138/C

C. 蘑菇侏儒 - 2

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

有一天,娜塔莉亚在树林里散步时遇到了一只小蘑菇侏儒。侏儒给她讲了下面的故事:

每个人都知道蘑菇侏儒的力量在于生长在侏儒原生森林中的魔法蘑菇。树林里有n棵树和m个神奇蘑菇:第i棵树生长在坐标为ai的直线上的一点,高度为hi,第j个蘑菇生长在坐标为bj的点,具有神奇的能力zj。

但是有一天,野生蘑菇咀嚼者,蘑菇侏儒的死敌,在他们的家乡森林中发动了一场可怕的风暴。结果,一些树木开始倒下,压碎了魔法蘑菇。蘑菇侏儒的最高神谕提前计算出每棵树向左、向右倒下或站立的概率。如果坐标为 x、高度为 h 的树向左倒下,则属于右开区间 [x - h, x) 的所有蘑菇都会被破坏。如果一棵树向右倒下,那么属于左开区间 (x, x + h] 的蘑菇就会被破坏。只有那些没有被单棵树击中的蘑菇才能生存。

知道所有的树都是相互独立倒下的(即所有事件都是相互独立的,而且这些树不会干扰其他向任意方向倒下的树),至高神谕也能够快速计算出暴风雨后幸存蘑菇的总力量的预期。他的计算最终使蘑菇侏儒免于濒临死亡。

Natalia,作为一名优秀的奥林匹克程序员,对这个故事很感兴趣,她决定想出一种方法来快速计算幸存蘑菇力量总和的期望。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 105, 1 ≤ m ≤ 104)——分别是树和蘑菇的数量。

接下来的 n 行每行包含四个整数 — ai, hi, li, ri (|ai| ≤ 109, 1 ≤ hi ≤ 109, 0 ≤ li, ri, li + ri ≤ 100),分别代表第 i 棵树的坐标、树的高度、树向左和向右倒下的概率的百分比(剩余的百分比是树站立的概率)。

接下来的 m 行每行包含两个整数 bj, zj (|bj| ≤ 109, 1 ≤ zj ≤ 103),分别代表第 j 个蘑菇的坐标和魔力。

一个点可以生长任意数量的树木和蘑菇。

输出

打印一个实数——对幸存蘑菇总魔力的期望。结果以相对或绝对精度 10 - 4 被接受。

示例

输入 #1

1 1
2 2 50 50
1 1

输出 #1

0.5000000000

输入 #2

2 1
2 2 50 50
4 2 50 50
3 1

输出 #2

0.2500000000

注意

认为坐标为 x 的蘑菇属于右开区间 [l, r) 当且仅当 l ≤ x < r。类似地,坐标为 x 的蘑菇属于左开区间 (l, r] 当且仅当 l < x ≤ r。

在第一次测试中,蘑菇存活的概率为 50%,具体取决于单棵树倒下的位置。

在第二个测试中,只有两棵树都没有落在蘑菇上,蘑菇才能存活。发生的概率为 50% × 50% = 25%。

预测试 12 是一个大型测试,有 105 棵树和一个蘑菇。