分数: 900 点
问题陈述
你负责控制大坝。大坝最多可蓄水 L 升水。最初,大坝是空的。每天早上都会有一定量的水流入大坝,每晚可以排出任意数量的水,但需要设定这个量,以便第二天早上没有水溢出大坝。
据了解, v_i 升水 t_i 摄氏度 将于明天上午流入大坝 i- 第一天。 您想知道每天中午大坝中水的最高可能温度,在需要准确的情况下 L 当时大坝中的水量为升。 i,求中午中午大坝内水的最高可能温度 i第一天。这里,分别考虑各个最大化,即为了使上层温度最大化而排出的水量 i- 第天,为达到最高温度而排出的水量可能有所不同 j第一天 (j≠i).
另外,假设除了流入大坝的新水之外,水温不受任何因素影响。也就是说,当 V_1 升水 T_1 摄氏度和 V_2 升水 T_2 摄氏度混合在一起,就会变成 V_1+V_2 升水 \frac{T_1*V_1+T_2*V_2}{V_1+V_2} 摄氏度,水的体积和温度不受任何其他因素的影响。
约束
- 1≤ N ≤ 5*10^5
- 1≤ L ≤ 10^9
- 0≤ t_i ≤ 10^9(1≤i≤N)
- 1≤ v_i ≤ L(1≤i≤N)
- v_1 = L
- L,每个 t_i 和 v_i 是整数。
输入
输入由标准输入按以下格式给出:
N L t_1 v_1 t_2 v_2 : t_N v_N
输出
打印 N 行。的 i第行应包含可以存储的最高温度 L 中午时大坝中该温度下的水升数 i- 第一天。
如果绝对或相对误差最多为,则接受每个值 10^{-6}.
示例输入 1
3 10 10 10 20 5 4 3
示例输出 1
10.0000000 15.0000000 13.2000000
-
第一天,大坝的水温始终是 10 度:第一天流入大坝的唯一水的温度。
-
10 升水 15 摄氏度可在第二天通过放电存储 第一天晚上 5 升水,将剩余的水与第二天流入大坝的水混合。
-
10 升水 13.2 摄氏度可在第三天存储,通过放电 第一天晚上 8 升水,将剩余的水与第二天和第三天流入大坝的水混合。
示例输入 2
4 15 0 15 2 5 3 6 4 4
示例输出 2
0.0000000 0.6666667 1.8666667 2.9333333
示例输入 3
4 15 1000000000 15 9 5 8 6 7 4
示例输出 3
1000000000.0000000 666666669.6666666 400000005.0000000 293333338.8666667
虽然水温可能超过 100 摄氏度,我们假设水不会蒸发。