题意：

两个人分别有$n$，$m$杯糖水，第一个人的第$i$杯有$a[i]$克糖，$b[i]$克水，第二个人的第$i$杯有$c[i]$克糖，$d[i]$克水。现在从两个人手中各取一杯糖水混合，有$nm$种可能的情况，求出其中浓度第$k$大的那一杯的浓度

Solution：

不妨先考虑这样一个问题：

两个数组各取一个元素，乘积有$nm$种，求出其中第$k$大的结果

直接二分答案，检查二分的答案在所有的情况排名第几，即有多少$(i,j)$有
$$a[i]\ast b[j]>mid$$
只需要固定$i$，二分符合这个$i$的$j$的数量即可，单次check的时间复杂度是$O(nlogn)$

这样只需要找到最后一个排名为$k$的数即可，总复杂度$O(nlognlogr)$，$r$是二分答案的长度

按照上述的思路，我们不妨也考虑二分答案

只需要找到有多少$(i,j)$有
$$\frac{a[i]+c[j]}{a[i]+b[i]+c[j]+d[j]}>mid$$
注意对一杯糖水并不是加浓度更高的糖水浓度就一定更高

此时把$(2)$改写成：
$$a[i]+c[j]>mid(a[i]+b[i]+c[j]+d[j])\times mid$$
下标分类，有
$$(1-mid)\times a[i]-mid\times b[i]>(mid-1)\times c[j]+mid\times d[j]$$
每次check只需要预先计算右式，排序后枚举$i$在右式上二分即可了

#include<iostream>
#include<utility>
#include<vector>
#include<cstdlib>
#include<numeric>
#include<unistd.h>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>
#include<stack>
#include<utility>
#include<cctype>
#include<cassert>
#include<thread>
#include<future>
#include<bitset>
#include<thread>
#include<random>
using namespace std;using ll=long long;
const int N=5e4+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=1e9+7;#define double long doublestruct sugar {int m1,m2;
}a[N],b[N];int n,m,k;
const double eps=1e-19;int cmp(double x,double y) {if(fabs(x-y)<eps) return 0;return x-y>eps?1:-1;
}double val[N];int get_rank(double p) {for(int i=1;i<=m;i++) val[i]=(p-1)*b[i].m1+p*b[i].m2;sort(val+1,val+1+m);int ret=0;for(int i=1;i<=n;i++) {double value=(1-p)*a[i].m1-p*a[i].m2;int it=lower_bound(val+1,val+1+m,value)-val;ret+=it-1;}return ret+1;
}int main() {#ifdef stdjudgefreopen("in.txt","r",stdin);auto TimeFlagFirst=clock();#endifstd::ios::sync_with_stdio(false);std::cin.tie(nullptr);cin>>n>>m>>k;for(int i=1;i<=n;i++) {cin>>a[i].m1>>a[i].m2;}for(int i=1;i<=m;i++) {cin>>b[i].m1>>b[i].m2;}double l=0,r=1,ans=0;for(int i=1;i<=200;i++) {double mid=(l+r)/2;if(get_rank(mid)<=k) {ans=mid;r=mid;} else l=mid;}printf("%.15Lf",100*ans);#ifdef stdjudgefreopen("CON","r",stdin);std::cout<<std::endl<<"耗时:"<<std::clock()-TimeFlagFirst<<"ms"<<std::endl;std::cout<<std::flush;system("pause");#endifreturn 0;
}