【题意】
给定两个集合 \(S,T\)，集合里每个元素都是一个二元组 \((v_i, s_i)\)。求 \(\min \limits_{i \in [1, |S|], j \in [1, |T|] }{\cfrac{s_j - s_i}{v_j + v_i}}\)。
\(|S|, |T| \le 10^5, v_i > 0\)
【分析】
一个基本方向是把式子拆成一边和 \(i\) 有关一边和 \(j\) 有关的。但是发现并不能直接化简。
使用二分答案解决。考虑答案是否大于等于 \(mid\)。
怎么验证：如果大于等于，那么对任意 \(i,j\) 均有 \(\cfrac{s_j - s_i}{v_j + v_i} \ge ans\)。
\[\cfrac{s_j - s_i}{v_j + v_i} \ge ans \\ s_j - s_i \ge ans \times (v_j +v_i) \\ s_j - ans \times v_j \ge s_i +ans \times v_i \]因此得知 \(ans\)，可以遍历一遍验证。
【思考】
这个问题里面二分的用意是什么？我们有 \(\min\)，我们将其消掉。
（我也搞不清楚为什么这样想，但是确实可以这么做）