← 返回题目列表

AtCoder · abc294_f

I. 糖水2

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

高桥和青木有 N 和 M 两瓶糖水。
高桥的 i-th糖水由以下组成 A_i 克糖和 B_i 克水。
青木的 i-th糖水由以下组成 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}.


示例输入 1

3 1 1
1 2
4 1
1 4
1 4

示例输出 1

50.000000000000000

让 (i, j) 表示通过混合高桥的糖水获得的 i第糖水和青木的 j-th。
以下是可以获得的糖水及其糖浓度。

  • (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 2
6 4
10 1
5 8
9 6

示例输出 2

62.500000000000000

示例输入 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