拦截导弹（加强） ### 题目描述 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。 我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。 ### 输入描述 第一行包含一个正整数 $n$，表示敌军导弹数量； 下面 行按顺序给出了敌军所有导弹信息： 第 $i+1$ 行包含 $2$ 个正整数 $h_i$ 和 $v_i$，分别表示第枚导弹的高度和速度。 其中，$1 \leq n \leq 5 \times 10^4， 1 \leq h_i,v_i \leq 10^9$。 ### 输出描述 输出包含两行。 第一行为一个正整数，表示最多能拦截掉的导弹数量； 第二行包含 $n$ 个 $0$ 到 $1$ 之间的实数，第 $i$ 个数字表示第 $i$ 枚导弹被拦截掉的概率（你可以保留任意多位有效数字）。 ### 输入输出样例 #### 示例 1 >输入 ```txt 4 3 30 4 40 6 60 3 30 ``` >输出 ```txt 2 0.33333 0.33333 0.33333 1.00000 ```