103566: [Atcoder]ABC356 G - Freestyle

Problem Statement

Takahashi can swim in $N$ different styles.
When he swims in the $i$-th style, he consumes $A_i$ stamina per second and advances $B_i$ meters per second.

Answer $Q$ queries. The $i$-th query is as follows:

• Determine if it is possible to advance $D_i$ meters while keeping the total stamina consumption at most $C_i$. If it is possible, find the minimum number of seconds required.

Here, he can freely combine different swimming styles, and the time to switch styles is negligible.
Specifically, he can swim using the following steps:

• Choose a positive integer $m$, a sequence of positive real numbers $t=(t_1,t_2,\dots,t_m)$ of length $m$, and a sequence of integers $x=(x_1,x_2,\dots,x_m)$ of length $m$ where each element is between $1$ and $N$, inclusive.
• Then, swim in the $x_i$-th style for $t_i$ seconds in the order $i=1,2,\dots,m$.

Constraints

• All input values are integers.
• $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$

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines in total.
For the $i$-th query, print the answer in the $i$-th line as follows:

• If it is impossible to advance $D_i$ meters while keeping the total stamina consumption at most $C_i$, print -1.
• Otherwise, print the minimum required time. The output is considered correct if the absolute or relative error between the printed value and the true answer is at most $10^{-9}$.

Sample Input 1

4
1 2
2 3
3 3
4 4
5
4 7
7 7
49 100
1000 500
4 5

Sample Output 1

3.000000000000000000
1.750000000000000000
-1
125.000000000000000000
1.500000000000000000

In this input, Takahashi can swim in the following four styles:

• Consumes $1$ stamina and advances $2$ meters per second.
• Consumes $2$ stamina and advances $3$ meters per second.
• Consumes $3$ stamina and advances $3$ meters per second.
• Consumes $4$ stamina and advances $4$ meters per second.

This input contains five queries.

• For the first query, $C_1=4, D_1=7$.
  • Choose $t=(1,2)$ and $x=(2,1)$. Takahashi swims as follows:
    • In the first $2$ seconds, he consumes $2$ stamina and advances $4$ meters.
    • In the next $1$ second, he consumes $2$ stamina and advances $3$ meters.
  • In total, he consumes $4$ stamina and advances $7$ meters. The required time is $3$ seconds, which is the minimum.
• For the second query, $C_2=7, D_2=7$.
  • Choose $t=(7/4)$ and $x=(4)$. Takahashi swims as follows:
    • In the first $7/4$ seconds, he consumes $7$ stamina and advances $7$ meters.
  • In total, he consumes $7$ stamina and advances $7$ meters. The required time is $7/4$ seconds, which is the minimum.
• For the third query, $C_3=49, D_3=100$.
  • No matter how Takahashi swims, it is not possible to advance $100$ meters while keeping the total stamina consumption at most $49$.
• For the fourth query, $C_4=1000, D_4=500$.
  • Choose $t=(125)$ and $x=(4)$. Takahashi swims as follows:
    • In the first $125$ seconds, he consumes $500$ stamina and advances $500$ meters.
  • In total, he consumes $500$ stamina and advances $500$ meters. The required time is $125$ seconds, which is the minimum.
• For the fifth query, $C_5=4, D_5=5$.
  • Choose $t=(1/2,1)$ and $x=(4,2)$. Takahashi swims as follows:
    • In the first $1/2$ seconds, he consumes $2$ stamina and advances $2$ meters.
    • In the next $1$ second, he consumes $2$ stamina and advances $3$ meters.
  • In total, he consumes $4$ stamina and advances $5$ meters. The required time is $3/2$ seconds, which is the minimum.

问题描述

高桥能以$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$之间（含）。
• 然后，按照顺序以第$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$行打印答案：

• 如果不可能在总体力消耗不超过$C_i$的情况下前进$D_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)$。高桥游泳如下：
    • 在前$2$秒，他消耗$2$体力，前进$4$米。
    • 接下来$1$秒，他消耗$2$体力，前进$3$米。
  • 总共，他消耗$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$秒，这是最短的。