Submission #19556468

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

template <class A, class B> bool cmin(A& a, B b) { return a > b && (a = b, true); }
template <class A, class B> bool cmax(A& a, B b) { return a < b && (a = b, true); }

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  vector<pair<int, int>> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i).first >> A.at(i).second;
  vector<pair<int, int>> B(M);
  for (int i = 0; i < M; i++) cin >> B.at(i).first >> B.at(i).second;

  auto f = [&](auto mid) {
    vector<double> V;
    for (const auto& [a, b] : A) V.push_back(b - a * mid);
    double mx = -1e10;
    for (const auto& [a, b] : B) cmax(mx, b - a * mid);
    V.push_back(mx);
    sort(V.rbegin(), V.rend());
    return accumulate(V.begin(), V.begin() + 5, 0.0) >= 0;
  };
  double ok = -1e10, ng = 1e10;
  for (int i = 0; i < 300; i++) {
    double mid = (ok + ng) / 2;
    (f(mid)) ? ok = mid : ng = mid;
  }
  cout << fixed << setprecision(6) << ok << '\n';
}

Submission Info

Judge Result