当前没有测试数据。

F - 糖水2

分数：500 分

问题描述

高桥和青木分别有 $N$ 个和 $M$ 个糖水瓶。
高桥的第 $i$ 个糖水由 $A_i$ 克糖和 $B_i$ 克水组成。
青木的第 $i$ 个糖水由 $C_i$ 克糖和 $D_i$ 克水组成。
有 $NM$ 种方法可以选择一种高桥的糖水和一种青木的糖水并混合它们。在这种方式下可以获得的 $NM$ 种糖水中，找到第 $K$ 高糖浓度的糖水的糖浓度。
这里，由 $x$ 克糖和 $y$ 克水组成的糖水的糖浓度为 $\dfrac{100x}{x+y}$ 百分比。我们会忽略饱和度。

约束

• $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$
• 输入中的所有值均为整数。

输入

从标准输入读取如下格式的输入：

$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

设 $(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$ 百分比。

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