\(\boldsymbol{a} := \begin{pmatrix} A _ 1 & A _ 2 & \dots & A _ N \end{pmatrix} ^ \top \in \mathbb{R} ^ N, \boldsymbol{b} := \begin{pmatrix} B _ 1 & B _ 2 & \dots & B _ N \end{pmatrix} ^ \top \in \mathbb{R} ^ N\) とすると，各クエリは以下のような線形計画問題として表せます．

\[ \begin{alignedat}{5} \min _ {\boldsymbol{x} \in \mathbb{R}^{N}} & \quad && \boldsymbol{1}^\top \boldsymbol{x} \\ \mathrm{s.t.} & \quad && \boldsymbol{a}^\top \boldsymbol{x} \le C \\ &&& \boldsymbol{b}^\top \boldsymbol{x} \ge D \\ &&& \boldsymbol{x} \ge \boldsymbol{0} \end{alignedat} \]

ここで，線形計画問題には強双対性が成立し，双対問題

\[ \begin{alignedat}{5} \max _ {\boldsymbol{y} \in \mathbb{R}^{2}} & \quad && \begin{pmatrix} - C & D \end{pmatrix} \boldsymbol{y} \\ \mathrm{s.t.} & \quad && \begin{pmatrix} - \boldsymbol{a} & \boldsymbol{b} \end{pmatrix} \boldsymbol{y} \le \boldsymbol{1} \\ &&& \boldsymbol{y} \ge \boldsymbol{0} \end{alignedat} \]

の答えは考えたい主問題の答えに等しいです． 変数の個数が \(N\) 個から \(2\) 個になり考えやすくなりました． \(\boldsymbol{y} = \begin{pmatrix} y _ 1 & y _ 2 \end{pmatrix} ^ \top\) として書き下すと

\[ \begin{alignedat}{5} \max _ {y _ 1, y _ 2 \in \mathbb{R}} & \quad && - C y _ 1 + D y _ 2 \\ \mathrm{s.t.} & \quad && - A _ i y _ 1 + B _ i y _ 2 \le 1 \quad (i = 1, \dots , N) \\ &&& y _ 1, y _ 2 \ge 0 \end{alignedat} \]

となります． 双対問題の答えが非有界のとき，主問題は実行不可能です．

\(\displaystyle - A _ i y _ 1 + B _ i y _ 2 \le 1 \ (i = 1, \dots , N) \iff y _ 2 \le \min_{i = 1, \dots , N} \left( \frac{A _ i}{B _ i} y _ 1 + \frac{1}{B _ i} \right)\) です． \(D \gt 0\) より，\(y _ 1\) を固定すると目的関数を最大化する \(y _ 2\) は取り得る最大値 \(\displaystyle y _ 2 = \min_{i = 1, \dots , N} \left( \frac{A _ i}{B _ i} y _ 1 + \frac{1}{B _ i} \right)\) で，これを \(f(y _ 1)\) とします． \(f\) は凹関数で，これを成す線分群は Convex Hull Trick と同様の手法で求めることができます．

\(\displaystyle - C y _ 1 + D y _ 2 = D\left( f(y _ 1) - \frac{C}{D} y _ 1 \right)\) であり，括弧の中身を \(g _ k(y _ 1) := f(y _ 1) - k y _ 1\) とするとこれも凹関数です． ここで，\(\argmax g _ k(y _ 1)\) は \(k\) について単調減少となります（ABC218-H 解説の解法 3 と同様に示すことができます）． また，\(\argmax g _ k(y _ 1)\) は先程求めた線分群の隣接する線分同士の交点となるため，クエリを \(\displaystyle \frac{C}{D}\) の昇順に並べて \(\argmax g _ k(y _ 1)\) となる交点を求めて処理することができます（\(y _ 1 \ge 0\) に注意する必要があります）．

サンプルの 1, 5 個目のクエリの最適解に対応しています

時間計算量は \(\mathrm{O}(N \log N)\) です（提出）．