比赛场次 553
比赛名称 2022级DP专题练习赛3
比赛状态 已结束比赛成绩
开始时间 2023-02-17 18:30:00
结束时间 2023-02-17 22:00:00
开放分组 全部用户
注释介绍 以赛代练
题目名称 拦截导弹
输入输出 sdoi2011_daodan.in/out
时间限制 1500 ms (1.5 s)
内存限制 512 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分
Gravatarzxhhh TTAAATTATTTTTTATATTT
21.010 s 6.32 MiB 30

拦截导弹

★★★☆   输入文件:sdoi2011_daodan.in   输出文件:sdoi2011_daodan.out   简单对比
时间限制:1.5 s   内存限制:512 MiB

【题目描述】

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


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


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

【输入格式】

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


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


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

【输出格式】

输出包含两行。

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

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

【样例1输入】

4
3 30
4 40
6 60
3 30

【样例1输出】

2
0.33333 0.33333 0.33333 1.00000

【样例2】

点击下载样例2

【数据规模与约定】

对于 $30\%$ 的数据,$1 \leq n \leq 1000$;

对于 $100\%$ 的数据,$1 \leq n \leq 5 \times 10^4,1 \leq h_i,v_i \leq 10^9$;

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

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

【来源】

SDOI 2011