まず、この問題のように 「集合の中で大きい方から \(K\) 番目の値を求めてください」といった問題では次のような性質が成り立ちます。

• 答を \(x\) とする。このとき、
  • \(x \lt y\) である \(y\) について、集合内に含まれる \(y\) 以上の要素の個数は \(K\) 未満である。
  • \(x \gt y\) である \(y\) について、集合内に含まれる \(y\) 以上の要素の個数は \(K\) 以上である。

よって、\(K\) 番目の値を求める問題は、

• \(y\) が与えられる。集合内に含まれる \(y\) 以上の要素の個数は \(K\) 未満 or \(K\) 以上のどちらか？

という判定問題を利用すると、判定問題 + 二分探索 で解くことができるようになります。このように判定問題に言い換えるテクニックは幅広い用途があるので、知らなかった人はぜひ覚えましょう。

判定問題を考えます。すなわち次のような問題です。

• 濃度 \(x\) が与えられる。\(NM\) 通りの砂糖水のうち濃度が \(x\) 未満である砂糖水は何本あるか？

(以下の説明での濃度はパーセンテージではなく単なる質量濃度を用います。) 判定問題は、「各砂糖水が濃度 \(x\) になるために砂糖がどれだけ足りないか？/余っているか？」に注目して解くことができます。

砂糖 \(s\) グラム, 水 \(t\) グラムの砂糖水を考えます。この砂糖水は、砂糖の量が \(s\) グラムではなく \(t \times \frac{x}{1 - x}\) だったらちょうど濃度 \(x\) でした。(濃度 \(x\) の砂糖水の砂糖と水の比は \(x\) 対 \(1-x\) なのを利用しています。) よって、\(u = t \times \frac{x}{1 - x}\) として、

• \(s \geq u\) の場合：砂糖が \(s-u\) グラム余っている。
• \(s \leq u\) の場合：砂糖が \(u - s\) グラム足りない。

という風に考えられます。2 番目の場合について、「(正の数)グラム足りない」ことを「(負の数) グラム余っている」とみなすと、どちらの場合も 「\(s-u\) グラム余っている」ということになります。
そして、\(2\) つの砂糖水を混ぜたときに濃度 \(x\) 以上であるかどうかは、それぞれの砂糖水について上記の \(s-u\) を足し合わせた値が \(0\) 以上かどうかで求められます。 このような考察を利用すると、以下の手順で \(\mathrm{O}(N \log M)\) で判定問題を解くことができます。

• 青木君の持っている砂糖水について、上記の \(s-u\) をそれぞれ計算した列を \((v_1, v_2, \dots, v_M)\) とする。
• \(v\) をソートする。
• 高橋君の持っている砂糖水について 1 個ずつ次の操作を行う。
  • 今注目している砂糖水について、\(s - u\) の値を \(w\) とする。このとき、青木君の持っている砂糖水のうち混ぜると濃度が \(x\) 以上になるものは、\(v_j\) の値が \(-w\) 以上の砂糖水すべてである。これは列 \(v\) の値を二分探索して「どの要素から右が \(-w\) 以上か？」を調べることで、個数を \(\mathrm{O}(\log M)\) で計算できる。
• そして、全体の個数の総和が \(K\) 以上かどうかを判定する。

よって、判定問題が \(\mathrm{O}(N \log M)\) で解けたので、問題全体は二分探索内で判定問題を解く回数を \(X\) として \(\mathrm{O}(X N \log M )\) で解くことができました。

なお、\(X\) は一般的には \(100\) 程度の定数に設定するのが無難です。この問題の許容誤差は \(10^{-9}\) ですが、「\(2^{-30} \lt 10^{-9}\) だから \(X=30\) にする」 というような決め方は double 型の値の保持の仕組みを考えると誤った決め方で、この問題では \(X\) は少なくとも \(40\) 程度は必要であると準備者は考えています。

• 実装例(C++)

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  long long N, M, K;
  cin >> N >> M >> K;
  vector<long long> A(N), B(N), C(M), D(M);
  for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
  for (int i = 0; i < M; i++) cin >> C[i] >> D[i];
  double ng = 0, ok = 1;
  for (int iter = 0; iter < 100; iter++) {
    double x = (ng + ok) / 2;
    double z = x / (1 - x);
    vector<double> v(M);
    for (int i = 0; i < M; i++) v[i] = C[i] - D[i] * z;
    sort(begin(v), end(v));
    long long num = 0;
    for (int i = 0; i < N; i++) {
      double w = A[i] - B[i] * z;
      num += M - (lower_bound(begin(v), end(v), -w) - begin(v));
    }
    (num < K ? ok : ng) = x;
  }
  cout << fixed << setprecision(16) << ok * 100 << "\n";
}