当前没有测试数据。

无限背包问题

得分：600分

问题描述

有 $N$ 种物品，每种物品都有无限数量。第 $i$ 种物品的重量为 $A_i$，体积为 $B_i$，价值为 $C_i$。

在级别 $X$，高濑大辅可以携带总重量不超过 $X$ 且总体积不超过 $X$ 的物品。在此条件下，可以携带同一种物品的任意数量，也可以放弃某些种类的物品。

设 $f(X)$ 表示高濑大辅在级别 $X$ 可以携带的物品的最大总价值。可以证明极限 $\displaystyle\lim_{X\to \infty} \frac{f(X)}{X}$ 存在。请计算这个极限的值。

约束条件

• $1\leq N\leq 2\times 10^5$
• $10^8\leq A_i,B_i,C_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_N$ $B_N$ $C_N$

输出

输出答案。当与评测机的答案的绝对或相对误差不超过 $10^{-6}$ 时，你的输出将被认为是正确的。

2
100000000 200000000 100000000
200000000 100000000 100000000

0.6666666666666667

当 $X=300000000$ 时，高濑大辅可以携带总重量不超过 $300000000$ 且总体积不超过 $300000000$ 的物品。

他可以携带，例如，一份第 1 种物品和一份第 2 种物品。然后，物品的总价值为 $100000000+100000000=200000000$。这是可以达到的最大值，所以 $\dfrac{f(300000000)}{300000000}=\dfrac{2}{3}$。

可以证明 $\displaystyle\lim_{X\to \infty} \frac{f(X)}{X}$ 等于 $\dfrac{2}{3}$。因此，答案为 $0.6666666...$。

1
500000000 300000000 123456789

0.2469135780000000