#1240. 2244. [SDOI2011]拦截导弹

2244. [SDOI2011]拦截导弹

#2244. [SDOI2011]拦截导弹

题目描述

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹,但是以后每一发炮弹都不能高于前一发的高度,其拦截的导弹的飞行速度也不能大于前一发。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

在不能拦截所有的导弹的情况下,我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个,如果有多个最优方案,那么我们会随机选取一个作为最终的拦截导弹行动蓝图。

我方间谍已经获取了所有敌军导弹的高度和速度,你的任务是计算出在执行上述决策时,每枚导弹被拦截掉的概率。

输入格式

第一行包含一个正整数n,表示敌军导弹数量;

下面 行按顺序给出了敌军所有导弹信息:

第i+1行包含2个正整数hi和vi,分别表示第 枚导弹的高度和速度。

输出格式

输出包含两行。

第一行为一个正整数,表示最多能拦截掉的导弹数量;

第二行包含n个0到1之间的实数,第i个数字表示第i枚导弹被拦截掉的概率(你可以保留任意多位有效数字)。

样例

样例输入

4  

  

3 30  

  

4 40  

  

6 60  

  

3 30  

样例输出

2  

  

0.33333 0.33333 0.33333 1.00000  

  

【数据规模和约定】  

  

  

对于100%的数据,1≤n≤5*104, 1≤hi ,vi≤109;  

  

均匀分布着约30%的数据,所有vi均相等。  

  

均匀分布着约50%的数据,满足1≤hi ,vi≤1000。  

数据范围与提示

鸣谢kac提供sj程序!