102945: [Atcoder]ABC294 F - Sugar Water 2

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：3 Solved：0

Description

Score : $500$ points

Problem Statement

Takahashi and Aoki have $N$ and $M$ bottles of sugar water, respectively.
Takahashi's $i$-th sugar water is composed of $A_i$ grams of sugar and $B_i$ grams of water.
Aoki's $i$-th sugar water is composed of $C_i$ grams of sugar and $D_i$ grams of water.
There are $NM$ ways to choose one from Takahashi's sugar waters and one from Aoki's and mix them. Among the $NM$ sugar waters that can be obtained in this way, find the concentration of sugar in the sugar water with the $K$-th highest concentration of sugar.
Here, the concentration of sugar in sugar water composed of $x$ grams of sugar and $y$ grams of water is $\dfrac{100x}{x+y}$ percent. We will ignore saturation.

Constraints

  • $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$
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print the concentration of sugar in the sugar water with the $K$-th highest concentration of sugar in percent.
Your output will be considered correct if the absolute or relative error from the true value is at most $10^{−9}$.

Sample Input 1

3 1 1
1 2
4 1
1 4
1 4

Sample Output 1

50.000000000000000

Let $(i, j)$ denote the sugar water obtained by mixing Takahashi's $i$-th sugar water and Aoki's $j$-th.
Below are the sugar waters that can be obtained and their concentrations of sugar.

  • $(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 \%$

Among them, the sugar water with the highest concentration of sugar is $(1, 2)$, with a concentration of $50$ percent.

Sample Input 2

2 2 2
6 4
10 1
5 8
9 6

Sample Output 2

62.500000000000000

Sample Input 3

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

Sample Output 3

54.166666666666664

Input

题意翻译

高橋君有 $N$ 瓶糖水，青木君有 $M$ 瓶糖水。 高橋君的第 $i$ 瓶糖水有 $A_i$ 份糖 $B_i$ 份水。 青木君的第 $i$ 瓶糖水有 $C_i$ 份糖 $D_i$ 份水。 将两人的糖水各选一瓶混合有 $NM$ 种可能，求其中浓度第 $k$ 大的糖水浓度是多少。 有 $x$ 份糖和 $y$ 份水的糖水浓度是 $\dfrac{100x}{x+y}\%$。

Output

得分：500分 部分 问题描述 Takahashi 和 Aoki 分别有 $N$ 瓶和 $M$ 瓶糖水。 Takahashi 的第 $i$ 瓶糖水由 $A_i$ 克糖和 $B_i$ 克水组成。 Aoki 的第 $i$ 瓶糖水由 $C_i$ 克糖和 $D_i$ 克水组成。 有 $NM$ 种选择方法，从 Takahashi 的糖水中选择一瓶，从 Aoki 的糖水中选择一瓶并混合它们。通过这种方式可以获得 $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)$ 表示通过混合 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%。 样例输入 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

HINT

n种糖水和m种糖水，混合方式有m*n种，请问按照糖浓度排序后，第k大浓度是多少？

Source/Category

加入题单

算法标签：