提出 #39871771

---

ソースコード 拡げる

#include <algorithm>
#include <iomanip>
#include <iostream>
#define N 51000
#define ll long long
using namespace std;
int n, m, a[N], b[N], c[N], d[N];
ll k;
double va[N], vb[N];
bool check(double mid) {
  for (int i = 1; i <= n; i++)
    va[i] = a[i] - b[i] * mid;
  for (int i = 1; i <= m; i++)
    vb[i] = c[i] - d[i] * mid;
  sort(va + 1, va + n + 1);
  sort(vb + 1, vb + m + 1);
  ll tot = 0;
  for (int i = 1, j = m; i <= n; i++) {
    while (j && va[i] + vb[j] >= 0)
      j--;
    tot += m - j;
  }
  return tot >= k;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++)
    cin >> a[i] >> b[i], b[i] += a[i];
  for (int i = 1; i <= m; i++)
    cin >> c[i] >> d[i], d[i] += c[i];
  double l = 0, r = 1;
  while (r - l > 1e-11) {
    double mid = (l + r) / 2;
    if (check(mid)) {
      l = mid;
    } else {
      r = mid;
    }
  }
  cout << fixed << setprecision(20) << l * 100 << '\n';
  return 0;
}

提出情報

ジャッジ結果