分数: 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}.
示例输入 1
2 100000000 200000000 100000000 200000000 100000000 100000000
示例输出 1
0.6666666666666667
当 X=300000000,高桥最多可以携带总重量为 300000000 其总体积最多为 300000000.
例如,他可以携带一份 1-st 项目和一份副本 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....
示例输入 2
1 500000000 300000000 123456789
示例输出 2
0.2469135780000000