TouchStone
  Please Login
ログイン 登録
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4429
  • 問題
  • P4429[SDOI2011]拦截导弹
    制限 : 時間制限 : - MS   メモリ制限 : - KB  SPJ
    審判説明 : 3s,512m
    問題説明

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

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

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

    入力形式

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

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

    \(i+1\) 行包含 $2$ 个正整数 \(h_i\)\(v_i\) ,分别表示第 \(i\) 枚导弹的高度和速度。

    出力形式

    输出包含两行。

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

    第二行包含 \(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\times10^4, 1≤h_i ,v_i≤10^9\)

    均匀分布着约 $30%$ 的数据,所有 \(v_i\) 均相等。

    均匀分布着约 $50%$ 的数据,满足 $1≤h_i ,v_i≤1000$ 。