概要

公式解説の解法と大きな違いはないのですが，クエリで考えるべき状況が進む距離が定数 \(D\) であることに合わせて，「時間あたり」ではなく「距離あたり」のデータを持つことで，クエリの形が少し考えやすいものになっていると思います．

解説

入力で直接与えられているのは「1 秒あたりの体力・距離」です． これを適当に読み替えると，「距離 1 あたりの時間・体力」となります．

これらの与えられた情報を，\((x_i, y_i)\) と書きます．つまり，

• \(i\) 種類目の泳ぎ方で距離 \(1\) 進むときの時間を \(x_i\)
• \(i\) 種類目の泳ぎ方で距離 \(1\) 進むときの体力を \(y_i\)

とします．

すると，全種類の泳ぎ方を適切に混ぜて距離 \(1\) 進むときの時間・体力は，\(t_1 + \cdots + t_n = 1\) となる非負実数列を用いて

• 時間：\(x = \sum t_ix_i\)
• 体力：\(y = \sum t_iy_i\)

となります．距離 \(D\) 進む場合に作れる泳ぎ方は単にこの \(D\) 倍です．

なお，座標平面上の点 \(p_i\) を \(p_i(x_i,y_i)\) と定めると，このような \((x,y)\) は \((p_i)_{1\leq i\leq N}\) の凸結合（総和が \(1\) の非負実数係数による線形結合）全体です．図形的にはこれら \(N\) 点の凸包全体を得ることができます．

以上をもとに問題を言い換えると次の形になります：

• 点 \(p_1, \ldots, p_N\) が与えられる．凸包を \(\mathrm{conv}(p_1, \ldots, p_N)\) と書くことにする．
• クエリでは \((C,D)\) が与えられ，次を答える．
  • \((x,y)\in \mathrm{conv}(p_1, \ldots, p_N)\) であって \(Dx\leq C\) を満たすものは存在するか？
  • 存在するならば，そのような点に対する \(Dy\) の最小値を求めよ．

凸包を適切に扱ってもよいですし，下側凸包だけを求めておいてもよいでしょう．また，凸包の頂点の \(y\) 座標を単調減少になるように少し修正しておくと，単に凸包の境界上の点を答えるだけの問題となり考えやすいと思います．

この解法では座標が整数ではない点を多く扱うことになります．答えるものは基本的には誤差に頑強（robust）で，例えば凸包の計算時に誤差でほぼ同一直線上にある点の扱いに失敗しても問題は生じません．ただし，\(x=C/D\) が凸包と交わるか否かの判定だけは整数のみを用いて正しくやらないと誤答になるかもしれません．