本問: M - おまかせ
類題: D - 食塩水
平均の最大化は binary search.
\(f_{x} \in Bool\)を,\(x\)以上にできるときtrue, そうでないときにfalse とする.
お助け無しの場合
\(\sum_{i \in K} \frac{b_{i}}{a_{i}} \geq x \iff \sum_{i \in K} (b_{i} - x a_{i}) \geq 0 \). よって,配列 \(ary := [b_{i} - x a_{i}]_{i \in N}\)を降順ソートして大きい方から\(K\)個とればよい.
お助け有りの場合
お助け\(j \in M\)を使う候補に追加する. ary に \(d[j] - x c[j]\)を追加して,後は同様.
(候補に追加しただけで,実際にお助けを使うのが最善とは限らない.)
typedef long long ll;
const ll INFL = 1LL << 60;
#define srep(i,s,t) for (ll i = (s); i < (t); ++i)
#define rep(i,n) srep(i,0,(n))
#define all(x) (x).begin(),(x).end()
int main() {
ll n, m, k, q;
cin >> n >> m;
vll a(n), b(n);
rep(i,n) cin >> a[i] >> b[i];
vll c(m), d(m);
rep(i,m) cin >> c[i] >> d[i];
// j: お助けの index
// return x 以上にできるか
auto f = [&](double x, ll j = -1) -> bool {
rep(i,n){
ary[i] = b[i] - x * a[i];
}
if(j != -1){
ary.push_back(d[j] - x * c[j]);
}
sort(all(ary), greater<double>());
double s = 0;
rep(i,5) s += ary[i];
return s >= 0;
};
auto judge = [&](double x) -> bool {
bool g = false;
g |= f(x); // お助け無し
rep(j,m){
g |= f(x, j); // j: お助け を使う候補に入れる
}
return g;
};
// O(log(1e18)*n*log(n))
double ok, ng;
ok = 0, ng = 1e18;
while(abs(ok-ng) > 1e-10){
double md = (ok + ng)/2; // rem : double
if(judge(md)) ok = md;
else ng = md;
}
printf("%.10lf\n", ok);
return 0;
}