AT_abc356_g [ABC356G] Freestyle

题目描述

高桥可以游出 $N$ 种不同的风格。
当他用第 $i$ 式游泳时，每秒消耗 $A_i$ 体力，每秒前进 $B_i$ 米。

回答 $Q$ 个问题。 第 $i$ 次查询如下：

• 判断是否有可能在总体力消耗不超过 $C_i$ 的情况下前进 $D_i$ 米。如果可能，请找出所需的最少秒数。

在这里，他可以自由组合不同的泳姿，切换泳姿的时间可以忽略不计。
具体来说，他可以使用以下步骤游泳：

• 选择一个正整数 $m$ ，一个长度为 $m$ 的正实数序列 $t=(t_1,t_2,\dots,t_m)$ ，以及一个长度为 $m$ 的整数序列 $x=(x_1,x_2,\dots,x_m)$ ，其中每个元素都介于 $1$ 和 $N$ 之间（含）。
• 然后，按照 $i=1,2,\dots,m$ 的顺序，以第 $x_i$ 的方式游 $t_i$ 秒。

输入格式

输入内容由标准输入法提供，格式如下

$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

输入 #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 \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$

样例 $1$ 说明

在此输入中，高桥可以用以下四种方式游泳：

• 消耗 $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$ 秒，这是最小值。
• 第二个查询，$C_2=7, D_2=7$ 。
  • 选择 $t=(7/4)$ 和 $x=(4)$ 。高桥游程如下：
    • 在最初的 $7/4$ 秒内，他消耗了 $7$ 体力，前进了 $7$ 米。
  • 他总共消耗了 $7$ 体力，前进了 $7$ 米。所需的时间为 $7/4$ 秒，这是最小值。
• 第三个查询，$C_3=49, D_3=100$ 。
  • 无论高桥如何游泳，都不可能在总体力消耗不超过 $49$ 的情况下前进 $100$ 米。
• 第四个查询， $C_4=1000, D_4=500$ 。
  • 选择 $t=(125)$ 和 $x=(4)$ 。高桥游泳的情况如下：
    • 在前 $125$ 秒，他消耗了 $500$ 体力，前进了 $500$ 米。
  • 他总共消耗了 $500$ 体力，前进了 $500$ 米。所需的时间为 $125$ 秒，这是最小值。
• 第五个查询， $C_5=4, D_5=5$ 。
  • 选择 $t=(1/2,1)$ 和 $x=(4,2)$ 。高桥游程如下：
    • 在前 $1/2$ 秒，他消耗了 $2$ 体力，前进了 $2$ 米。
    • 在接下来的 $1$ 秒内，他消耗了 $2$ 点体力，前进了 $3$ 米。
  • 他总共消耗了 $4$ 体力，前进了 $5$ 米。所需的时间为 $3/2$ 秒，这是最短时间。