分数: 575 点
问题陈述
高桥可以游泳 N 不同的风格。
当他在水中游泳时 i第一种风格,他消耗 A_i 每秒耐力和进步 B_i 米每秒。
答案 Q 查询。的 i第查询如下:
- 判断是否可以前进 D_i 米,同时保持总体力消耗最多 C_i。如果可能的话,找出所需的最小秒数。
在这里,他可以自由组合不同的泳姿,而且切换泳姿的时间可以忽略不计。
具体来说,他可以按照以下步骤游泳:
- 选择一个正整数 m,正实数序列 t=(t_1,t_2,\dots,t_m) 长度 m,以及整数序列 x=(x_1,x_2,\dots,x_m) 长度 m 其中每个元素位于 1 和 N,包括在内。
- 然后,在 x_i-第样式 t_i 秒顺序 总共 i=1,2,\dots,m.
约束
- 所有输入值均为整数。
- 1 \le N \le 2 \times 10^5
- 1 \le A_i, B_i \le 10^9
- 1 \le Q \le 2 \times 10^5
- 1 \le C_i, D_i \le 10^9
输入
输入由标准输入按以下格式给出:
N A_1 B_1 A_2 B_2 \vdots A_N B_N Q C_1 D_1 C_2 D_2 \vdots C_Q D_Q
输出
打印 Q 行。
对于 i- 第一个查询,打印答案 i第行如下:
- 如果无法前进 D_i 米,同时保持总体力消耗最多 C_i,打印
-1. - 否则,打印所需的最短时间。如果打印值与真实答案之间的绝对或相对误差最多为,则输出被认为是正确的 10^{-9}.
示例输入 1
4 1 2 2 3 3 3 4 4 5 4 7 7 7 49 100 1000 500 4 5
示例输出 1
3.000000000000000000 1.750000000000000000 -1 125.000000000000000000 1.500000000000000000
在此输入中,高桥可以以以下四种方式游泳:
- 消耗 1 耐力和进步 2 米每秒。
- 消耗 2 耐力和进步 3 米每秒。
- 消耗 3 耐力和进步 3 米每秒。
- 消耗 4 耐力和进步 4 米每秒。
此输入包含五个查询。
- 对于第一个查询, C_1=4, D_1=7.
- 选择 t=(1,2) 和 x=(2,1)。高桥的游泳方式如下:
- 在第一个 1 第二,他消耗 2 耐力和进步 3 米。
- 在接下来 2 秒,他消耗 2 耐力和进步 4 米。
- 他总共消耗了 4 耐力和进步 7 米。所需时间为 3 秒,这是最小值。
- 选择 t=(1,2) 和 x=(2,1)。高桥的游泳方式如下:
- 对于第二个查询, C_2=7, D_2=7.
- 选择 t=(7/4) 和 x=(4)。高桥的游泳方式如下:
- 在第一个 7/4 秒,他消耗 7 耐力和进步 7 米。
- 他总共消耗了 7 耐力和进步 7 米。所需时间为 7/4 秒,这是最小值。
- 选择 t=(7/4) 和 x=(4)。高桥的游泳方式如下:
- 对于第三个查询, C_3=49, D_3=100.
- 无论高桥如何游动,都不可能晋级 100 米,同时保持总体力消耗最多 49.
- 对于第四个查询, C_4=1000, D_4=500.
- 选择 t=(125) 和 x=(4)。高桥的游泳方式如下:
- 在第一个 125 秒,他消耗 500 耐力和进步 500 米。
- 他总共消耗了 500 耐力和进步 500 米。所需时间为 125 秒,这是最小值。
- 选择 t=(125) 和 x=(4)。高桥的游泳方式如下:
- 对于第五个查询, C_5=4, D_5=5.
- 选择 t=(1/2,1) 和 x=(4,2)。高桥的游泳方式如下:
- 在第一个 1/2 秒,他消耗 2 耐力和进步 2 米。
- 在接下来 1 第二,他消耗 2 耐力和进步 3 米。
- 他总共消耗了 4 耐力和进步 5 米。所需时间为 3/2 秒,这是最小值。
- 选择 t=(1/2,1) 和 x=(4,2)。高桥的游泳方式如下: