Li Chao Tree を使う方法を紹介します。 Li Chao Tree は

1. $S$ に点 $(a,\ b)$ を追加する
2. $x$ を与えたとき $\max\{ax+b\ |\ (a,\ b) \in S\}$ を求める

ができるデータ構造です。参考： yaketake さんのブログ

本問では、 \(ax+by=b\cdot (\displaystyle\frac{\ a\ }{b}\cdot x+y)\) と考えると、点 \((x,\ y)\) たちを \(S\) に追加していき、クエリでは \(\displaystyle\frac{\ a\ }{b}\) における値を取得すれば良いです（上の 1. 2. の説明と文字の種類が逆なので注意）。

下記などに注意して実装するとこの問題を AC することができます。

• \(b\) の符号によってクエリで取得すべきものが最大値・最小値と入れ替わること
• \(b=0\) の場合はそのままでは処理できないこと
• 浮動小数点数を使うと誤差が生じること

AC コード（PyPy3）（誤差死を避けるため多倍長整数で雑に処理しています。）