← 返回题目列表

AtCoder · agc021_b

B. 孔

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

分数: 600 点

问题陈述

有 N 二维平面上的孔。的坐标 i第一个洞是 (x_i,y_i).

让 R=10^{10^{10^{10}}}。 Ringo 执行以下操作:

  • 从半径为圆的内部随机选择一个点 R 以原点为中心,并将 Snuke 放在那里。 Snuke会移动到距该点欧几里德距离最小的洞,并落入该洞。如果有多个这样的孔,则将选择索引最小的孔。

对于每个 i (1 \leq i \leq N),求Snuke落入的概率 i第一个洞。

这里是从半径为圆的内部随机选择一个点的操作 R 定义如下:

  • 选择两个实数 x 和 y 独立地根据均匀分布 [-R,R].
  • If x^2+y^2\leq R^2,重点 选择 (x,y) 。否则,重复选取实数 x,y 直到满足条件。

约束

  • 2 \leq N \leq 100
  • |x_i|,|y_i| \leq 10^6(1\leq i\leq N)
  • 所有给定点都是成对不同的。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1
:
x_N y_N

输出

打印 N 实数。的 i第一个实数必须代表 Snuke 落入 i第一个洞。

当所有输出值的绝对或相对误差至多时,将判断输出正确 10^{-5}.


示例输入 1

2
0 0
1 1

示例输出 1

0.5
0.5

如果林戈将 Snuke 放入该区域 x+y\leq 1,Snuke会掉进第一个洞。这种情况发生的概率非常接近 0.5。 否则,Snuke就会掉进第二个洞,发生的概率也非常接近 0.5.


示例输入 2

5
0 0
2 8
4 5
2 6
3 10

示例输出 2

0.43160120892732328768
0.03480224363653196956
0.13880483535586193855
0.00000000000000000000
0.39479171208028279727