← 返回题目列表

AtCoder · arc072_d

F. 坝

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

分数: 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 摄氏度,我们假设水不会蒸发。