F - Sugar Water 2 Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

高橋君は N 本の砂糖水を、青木君は M 本の砂糖水を持っています。
高橋君の持っている i 番目の砂糖水は砂糖 A_i グラムと水 B_i グラムからなります。
青木君の持っている i 番目の砂糖水は砂糖 C_i グラムと水 D_i グラムからなります。
2 人の持つ砂糖水をそれぞれ 1 本ずつ選んで混ぜる方法は 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) と表します。
あり得る砂糖水の混ぜ方とその濃度を列挙すると以下のようになります。

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

この中で濃度が高い方から 1 番目の砂糖水は (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

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 (2, 1), 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