AT_abc294_f [ABC294F] Sugar Water 2

题目描述

高桥君有 $N$ 瓶砂糖水，青木君有 $M$ 瓶砂糖水。
高桥君的第 $i$ 瓶砂糖水由 $A_i$ 克砂糖和 $B_i$ 克水组成。
青木君的第 $i$ 瓶砂糖水由 $C_i$ 克砂糖和 $D_i$ 克水组成。
两人各自选一瓶砂糖水混合，共有 $NM$ 种混合方式。在所有这些混合方式中，请求出按浓度从高到低排列时第 $K$ 高的砂糖水的浓度是多少百分比。
这里，含有 $x$ 克砂糖和 $y$ 克水的砂糖水的浓度为 $\dfrac{100x}{x+y}\ \%$。另外，假设所有砂糖都能完全溶解。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$ $K$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$
$C_1$ $D_1$
$C_2$ $D_2$
$\vdots$
$C_M$ $D_M$

输出格式

请输出按浓度从高到低排列时第 $K$ 高的砂糖水的浓度（百分比）。
如果你的答案与真实值的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

输入输出样例 #1

输入 #1

3 1 1
1 2
4 1
1 4
1 4

输出 #1

50.000000000000000

输入输出样例 #2

输入 #2

2 2 2
6 4
10 1
5 8
9 6

输出 #2

62.500000000000000

输入输出样例 #3

输入 #3

4 5 10
5 4
1 6
7 4
9 8
2 2
5 6
6 7
5 3
8 1

输出 #3

54.166666666666664

说明/提示

限制条件

• $1 \leq N, M \leq 5 \times 10^4$
• $1 \leq K \leq N \times M$
• $1 \leq A_i, B_i, C_i, D_i \leq 10^5$
• 输入的所有数值均为整数

样例解释 1

以下用 $(i, j)$ 表示高桥君的第 $i$ 瓶砂糖水和青木君的第 $j$ 瓶砂糖水混合得到的砂糖水。
所有可能的混合方式及其浓度如下：

• $(1, 1)$：$100 \times \frac{1 + 1}{(1 + 1) + (2 + 4)} = 25\%$
• $(2, 1)$：$100 \times \frac{1 + 4}{(4 + 1) + (1 + 4)} = 50\%$
• $(3, 1)$：$100 \times \frac{1 + 1}{(1 + 1) + (4 + 4)} = 20\%$ 在这些混合方式中，浓度最高的是 $(2, 1)$，其浓度为 $50\%$。

由 ChatGPT 4.1 翻译