P2487 [SDOI2011] 拦截导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。 我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。

无

无

保证总方案数不超过 C++ 中 double 类型的存储范围。 ### 数据范围及约定 - 均匀分布着约 $30\%$ 的数据，所有 $v_i$ 均相等； - 均匀分布着约 $50\%$ 的数据，满足 $1\le h_i,v_i\le 1000$。 - 对于 $30\%$ 的数据，满足 $1\le n\le 1000$； - 对于 $100\%$ 的数据，$1\le n\le 5\times 10^4$，$1\le h_i,v_i\le 10^9$。 ### 评分标准 对于每个测试点，若输出的第一行与标准输出相同，则得到该测试点 $40\%$ 的分数，若输出文件的第二行的每个数与标准输出的误差均不大于 $10^{-4}$，则得到该测试点 $60\%$ 的分数，两项相加作为该测试点总得分。