← 返回题目列表

AtCoder · code_festival_china_f

F. 烤肉

中文机器翻译题面 查看原题

问题

有一种日本菜叫“烤肉”,与烧烤非常相似。 您在烤架上烤一些肉来烹饪“烤肉”。

你有一个烤架,可以同时烤任意数量的肉。 你想做 N 使用那个烤架的“烤肉”。

“烤肉”是一道非常嫩的菜肴, i- 第一块肉当时必须放在烤架上 s_i,并且必须当时领取 t_i 锋利。如果你晚于 t_i 那块被“烧焦”了。如果你早于 t_i 那件作品“未完成”。

但是,当您选择 i当时的第块肉 t_i,你完全忘记了你把 i- 第一块肉上,等你挑 1 随机从烤架上取出一块肉。 计算每块肉被“未熟”和“烧焦”的概率。


输入

输入按以下格式给出。

N
s_1 t_1
s_2 t_2
:
s_N t_N
  • 在第一行,您将获得整数 N (1 \leq N \leq 100,000),您要烹饪“烤肉”的肉块数。
  • 正在关注 N 行由两个整数组成 s_i,t_i (0 \leq s_i < t_i \leq 10^9),您放置的时间 i烤架上的第肉以及您必须从烤架上拿起该肉的时间。 s_1,s_2,...,s_N,t_1,t_2,...,t_N 彼此不同。

输出

输出 N 行。的 i-th (1 \leq i \leq N) 行应包含以下概率 i从烤架上拿起的第块肉“未熟”且“烧焦”,间隔有空间。 如果您的答案的绝对或相对误差小于 10^{-7}.


输入示例 1

2
1 3
2 4

输出示例 1

0.0 0.5
0.5 0.0

想想 1一块肉。当时 3 有 2 烤架上的肉块。你选择 2nd 块肉的概率 1/2 在当时的情况下 4 这 1st 肉会被捡起“烧焦”。

想想 2一块肉。当时 3 这 2nd 块肉有概率从烤架上取出 1/2 并且“未完成”。


输入示例 2

5
1 2
3 4
5 10
6 9
7 8

输出示例 2

0.0000000000 0.0000000000
0.0000000000 0.0000000000
0.6666666667 0.0000000000
0.3333333333 0.3333333333
0.0000000000 0.6666666667

输入示例3

1
0 1000000000

输出示例 3

0 0