Sugar Water 2

题目描述

Takahashi 和 Aoki 分别有 $N$ 瓶和 $M$ 瓶糖水。
Takahashi 的第 $i$ 瓶糖水由 $A_i$ 克糖和 $B_i$ 克水组成。
Aoki 的第 $i$ 瓶糖水由 $C_i$ 克糖和 $D_i$ 克水组成。
从 Takahashi 的糖水中选一瓶、从 Aoki 的糖水中选一瓶并将它们混合，有 $NM$ 种选择方法。在通过这种方式可以得到的 $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}$ 时，视为正确。

3 1 1
1 2
4 1
1 4
1 4

50.000000000000000

2 2 2
6 4
10 1
5 8
9 6

62.500000000000000

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

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$ 输入中的所有数值均为整数。记 $(i, j)$ 表示由 Takahashi 的第 $i$ 瓶糖水与 Aoki 的第 $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$ 百分比。

标签: AtCoder|abc294F

来源

AtCoder|abc294F