ABC294F糖水两两组合求第k大浓度

k远远超过$ 10^8 $，不可能依次算出来，考虑二分答案，验证是否有足够多的浓度达到要求，如果有，那么答案更大，否则更小。
怎么统计有多少组合浓度达到m呢？
$ \frac a b \times \frac c d => \frac {a+c} {b+d} \ge m$
$ a+c \ge m(b+d) => a-mb >= md-c$
计算出md-c，依次枚举第一种糖水，二分查找统计有多少个小于等于a-mb的即可。

#include <bits/stdc++.h>
#define N 50050
using namespace std;
int i, j, k, x, y, a[N], b[N], c[N], d[N];
long long n, s;
double l, r, m, t, v[N];
int gou(){
    for(i=1; i<=y; i++){
        v[i] = m*d[i] - c[i];
    }//a-mb >= md-c
    sort(v+1, v+y+1);
    for(s=0, i=1; i<=x; i++){
        k = upper_bound(v+1, v+y+1, a[i]-m*b[i]) - v;
        s += k - 1;
    }//小于等于a[i]-m*b[i]即可
    return s >= n;
}
int main(){
    scanf("%d%d%lld", &x, &y, &n);
    for(i=1; i<=x; i++){
        scanf("%d%d", &a[i], &b[i]);
        b[i] += a[i];
    }
    for(i=1; i<=y; i++){
        scanf("%d%d", &c[i], &d[i]);
        d[i] += c[i];
    }
    l = 0, r = 1;
    while(r-l > 1e-13){
        m = (l+r) / 2;
        if(gou()) l = m;
        else r = m;
    }//二分浓度
    printf("%.10lf\n", r*100);
    return 0;
}