First of all, when it comes to “finding the \(K\)-th value of a set” as in this problem, we have the following properties:

• Let \(x\) be the answer. Then,
  • For all \(y\) such that \(x \lt y\), there are strictly less than \(K\) elements greater than or equal to \(y\) in the set.
  • For all \(y\) such that \(x \gt y\), there are at least \(K\) elements greater than or equal to \(y\) in the set.

Thus, one can find the \(K\)-th value with a decision problem, together with a binary search:

• You are given \(y\). Is there at least, or strictly less than, \(K\) elements greater than or equal to \(y\) in the set?

The technique of boiling down to a decision problem has a wide range of applications. If you did not know, learn it now!

Now we consider the decision problem. Specifically:

• You are given a concentration \(x\). Among among \(NM\) sugar waters, how many of them have concentrations strictly less than \(x\)?

(In the description below, we do not use percentage but just mass ratio to describe the concentration.) The decision problem can be solved by focusing on “how much sugar is needed for each sugar water to have a concentration \(x\)?”

Consider a sugar water composed of \(s\) grams of sugar and \(t\) grams of water. This sugar water would have had a concentration of exactly \(x\) if the amount of sugar were \(t \times \frac{x}{1 - x}\) grams instead of \(s\) grams. (Here we use the fact that the ratio of sugar to the water equals \(x\) to \((1-x)\) if the sugar water’s concentration is \(x\).) Therefore, with \(u = t \times \frac{x}{1 - x}\), we can say that:

• If \(s \geq u\): it has \((s-u)\) grams of excessive sugar.
• If \(s \leq u\): it lacks \((u-s)\) grams of sugar.

For the second case, instead of saying “it lacks (positive) grams of sugar,” we can say “it has (negative) grams of excessive sugar.” This way, it always has \((s-u)\) grams of sugar in both cases. With this observation, one can solve the decision problem in an \(\mathrm{O}(N \log M)\) time.

• Let \((v_1, v_2, \dots, v_M)\) be the sequence of \((s-u)\) defined above for each sugar water that Aoki has.
• Sort \(v\).
• Process each of Takahashi’s sugar water as follows.
  • Let \(w\) be the \((s-u)\) of the current sugar water. Then, Aoki’s sugar waters that yields a sugar water of concentration at least \(x\) by mixing are those whose \(v_j\) are at least \(-w\). The number of such sugar waters can be found in an \(\mathrm{O}(\log M)\) time with a binary search on \(v\) to determine “which is the leftmost element whose value is at least \(-w\)?”.
• Then, determine if the sum of the numbers are at least \(K\).

Now that the decision problem has been solved in an \(\mathrm{O}(N \log M)\) time, the entire problem has been solved in a total of \(\mathrm{O}(X N \log M )\) time, where \(X\) is the number of times that the decision problem is solved.

Generally, \(X\) is recommended to be around \(100\). While this problem accepts at most \(10^{-9}\) error, we cannot just “let \(X=30\) because \(2^{-30} \lt 10^{-9}\)”; the problemsetters think that \(X\) needs to be at least about \(40\).

• Sample code (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";
}