濃度を固定した方が簡単． また，2つしか混ぜない．
自然な解法． 濃度 \(z\) を固定したとき， 2つの砂糖水 \(i \in N, j \in M\) を混ぜて濃度を \(z\) 以上に出来ることは， \[ \frac{a_{i} + c_{j}}{a_{i} + b_{i} + c_{j} + d_{j}} \geq z \] と同値． これを \(i,j\) に分離すると， \[ a_{i} - z(a_{i} + b_{i}) \geq -(c_{j} + z(c_{j} + d_{j})) \cdots (*) \] と書ける． 右辺を \(e_{j}\) とおいて， \(e := [e_{j}]_{j \in M} \) をソートする．
\(i \in N\) を固定すれば，\*1;
*1:*)\) を満たす \(j\) の個数は binary search で\(O(log M)\) で求まる． あとは， \((*)\) を満たす \(\,(i, j)\,\) の個数が \(K\) 個以上になるかを判定すれば， \(z\) に関する binary search で求まる．
砂糖 \(s\), 水 \(t\) の濃度は \(x := s/(s+t)\). このとき，\(s : t = x : 1-x\) となる． よって，\(s = tx/(1-x)\) と書ける． 言い換えると， 濃度 \(x\) と水 \(t\) を固定すると， 必要な砂糖は \(tx/(1-x)\) となる．
砂糖水 \(\,(s, t)\,\) をとって，濃度 \(x\) をとると， この砂糖水が濃度 \(x\) 以上になるためには， 砂糖の余裕が \( f_{s,t} := s - tx/(1-x) \) あることになる． よって，2つの砂糖水 \(\,(a,b), (c,d)\,\) を混ぜたときに 濃度が \(x\) 以上であることは， \begin{eqnarray} && f_{a,b} + f_{c,d} \\ & = & f_{a+c, b+d} \\ & \geq & 0 \end{eqnarray} と同値． よって，\(e := [f_{c_{j}, d_{j}}]_{j \in M}\) をソートしておけば， 各 \(i \in N\) に対して，濃度が \(x\) 以上になる \(j \in M\) の個数が binary search で求まる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
