题目大意
高桥君有 \(N\) 瓶糖水，第 \(i\) 瓶有 \(A_i\) 克糖和 \(B_i\) 克水。青木君有 \(M\) 瓶糖水，第 \(i\) 瓶有 \(C_i\) 克糖和 \(D_i\) 克水。然后两人各拿出一瓶混在一起，求可能产生的第 \(K\) 大的浓度百分比是多少，误差在 \(10^{-9}\) 内均为正确。
定义一瓶 \(x\) 克糖 \(y\) 克水的糖水浓度为 \(\dfrac{100x}{x+y}\%\)。
\(1\le N,M\le 5\cdot 10^4\)，\(1\le K \le NM\)，\(1\le A_i,B_i,C_i,D_i\le 10^5\)，输入均为整数。
题目解析
考虑直接求第 \(K\) 大不好算，所以考虑二分答案，然后求一个浓度比他大的数量。
考虑两个瓶糖水混合在一起，浓度大于等于 \(t\)。
\[\dfrac{A_i+C_j}{A_i+B_i+C_j+D_j}\ge t
\]
考虑化简，将 \(A_i,B_i\) 和 \(C_j,D_j\) 分到不等式两边，得到
\[A_i-(A_i+B_i)t\ge-C_j+(C_j+D_j)t
\]
这样我们可以按照 \(-C_j+(C_j+D_j)t\) 排序，枚举 \(i\) 二分 \(j\) 即可做到 \(\Theta(N\log N)\) 计算。
加上前面二分答案，复杂度就是 \(\Theta(N\log M\log W)\)，其中 \(W=10^{12}\)。
坑点：
long double防止卡精度- \(K\) 的范围是 \(NM=2.5\cdot10^9\)，需要
long long
int n,m; ll k; ld l,r,mid,p[maxn],q[maxn];
struct JTZ{
ld x,y;
}a[maxn],b[maxn];
#define mg(i,j) ((a[i].x+b[j].x)*1.0/(a[i].x+a[i].y+b[j].x+b[j].y))
ll js(){
int i,le,ri,midd; ll cnt=0;
for(i=1;i<=n;i++) p[i]=a[i].x-(a[i].x+a[i].y)*mid;
for(i=1;i<=m;i++) q[i]=-b[i].x+(b[i].x+b[i].y)*mid;
sort(q+1,q+m+1);
for(i=1;i<=n;i++){
le=0,ri=m+1;
while(le+1<ri){
midd=(le+ri)>>1;
if(q[midd]<p[i]+1e-12) le=midd; else ri=midd;
}
cnt+=le;
} return cnt;
}
int main(){
n=read(); m=read(); k=read(); int i;
for(i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
for(i=1;i<=m;i++) b[i].x=read(),b[i].y=read();
l=0,r=1;
while(l+EPS<=r){
mid=(l+r)/2;
if(js()<k) r=mid; else l=mid;
}
printf("%.10Lf",l*100.0);
return 0;
}