G - Freestyle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 575 点

問題文

高橋くんは N 種類の泳ぎ方ができます。
高橋くんが i 種類目の泳ぎ方で泳ぐと、 1 秒あたり体力を A_i 消費して B_i [m] 進みます。

Q 個のクエリに答えてください。そのうち i 個目は次の通りです。

  • 消費する体力の合計を C_i 以下にして D_i [m] 進むことができるか判定し、進める場合は必要な最小の秒数を求めよ。

ただし、高橋くんは泳ぎ方を自由に組み合わせることができ、泳ぎ方を変える時間は無視できます。
具体的には、次の手順で泳ぐことができます。

  • 正整数 m 、全ての要素が正である長さ m の実数列 t=(t_1,t_2,\dots,t_m) 、全ての要素が 1 以上 N 以下の長さ m の整数列 x=(x_1,x_2,\dots,x_m) を選択する。
  • その後、 i=1,2,\dots,m の順で、 x_i 種類目の泳ぎ方で t_i 秒間泳ぐ。

制約

  • 入力は全て整数
  • 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 [m] 進むことができない場合、 -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

この入力において、高橋くんは以下の 4 種類の泳ぎ方ができます。

  • 1 秒あたり体力を 1 消費して 2 [m] 進む。
  • 1 秒あたり体力を 2 消費して 3 [m] 進む。
  • 1 秒あたり体力を 3 消費して 3 [m] 進む。
  • 1 秒あたり体力を 4 消費して 4 [m] 進む。

この入力にはクエリが 5 個含まれます。

  • 1 個目の質問では、 C_1=4,D_1=7 です。
    • t=(1,2),x=(2,1) と選択します。このとき高橋くんは次の通りに泳ぎます。
      • 最初の 1 秒で高橋くんは体力を 2 消費して 3 [m] 進みます。
      • 次の 2 秒で高橋くんは体力を 2 消費して 4 [m] 進みます。
    • このとき、高橋くんは全体で体力を 4 消費して 7 [m] 進みました。この場合の所要時間は 3 秒で、これが達成可能な最小です。
  • 2 個目の質問では、 C_2=7,D_2=7 です。
    • t=(7/4),x=(4) と選択します。このとき高橋くんは次の通りに泳ぎます。
      • 最初の 7/4 秒で高橋くんは体力を 7 消費して 7 [m] 進みます。
    • このとき、高橋くんは全体で体力を 7 消費して 7 [m] 進みました。この場合の所要時間は 7/4 秒で、これが達成可能な最小です。
  • 3 個目の質問では、 C_3=49,D_3=100 です。
    • 高橋くんがどのような泳ぎ方をしても、消費する体力の合計を 49 以下にして 100 [m] 進むことはできません。
  • 4 個目の質問では、 C_4=1000,D_4=500 です。
    • t=(125),x=(4) と選択します。このとき高橋くんは次の通りに泳ぎます。
      • 最初の 125 秒で高橋くんは体力を 500 消費して 500 [m] 進みます。
    • このとき、高橋くんは全体で体力を 500 消費して 500 [m] 進みました。この場合の所要時間は 125 秒で、これが達成可能な最小です。
  • 5 個目の質問では、 C_5=4,D_5=5 です。
    • t=(1/2,1),x=(4,2) と選択します。このとき高橋くんは次の通りに泳ぎます。
      • 最初の 1/2 秒で高橋くんは体力を 2 消費して 2 [m] 進みます。
      • 次の 1 秒で高橋くんは体力を 2 消費して 3 [m] 進みます。
    • このとき、高橋くんは全体で体力を 4 消費して 5 [m] 進みました。この場合の所要時間は 3/2 秒で、これが達成可能な最小です。

Score : 575 points

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 1 second, he consumes 2 stamina and advances 3 meters.
      • In the next 2 seconds, he consumes 2 stamina and advances 4 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.