B - Holes Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600 点

問題文

平面上に N 個の穴があります。i 個目の穴の座標は、(x_i,y_i) です。

R=10^{10^{10^{10}}} とします。りんごさんは、以下の操作を行います。

  • 原点を中心とする半径 R の円内から無作為に 1 点を選び、すぬけ君を置く。すぬけ君は、置かれた点からユークリッド距離が最も近い穴に移動し、落ちる。そのような穴が複数ある場合は、添え字の最も小さいものを選ぶ。

全ての 1\leq i\leq N に対し、すぬけ君が i 番目の穴に落ちる確率を求めてください。

ただし、半径 R の円内から無作為に 1 点を選ぶ操作とは、以下の操作を指します。

  • [-R,R] 上の独立な一様分布にしたがって実数 x,y を選ぶ。
  • もし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 個目の実数は、すぬけ君が i 番目の穴に落ちる確率を表さなければならない。

出力されたすべての値について絶対誤差あるいは相対誤差が 10^{-5} 以下のとき、正答と判定される。

入力例 1

2
0 0
1 1

出力例 1

0.5
0.5

りんごさんが x+y\leq 1 なる領域にすぬけ君を置いた場合、すぬけ君は 1 番目の穴に落ちます。このような確率は 0.5 に非常に近いです。 また、そうでない場合すぬけ君は 2 番目の穴に落ち、そのような確率も 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

Score : 600 points

Problem Statement

There are N holes in a two-dimensional plane. The coordinates of the i-th hole are (x_i,y_i).

Let R=10^{10^{10^{10}}}. Ringo performs the following operation:

  • Randomly choose a point from the interior of a circle of radius R centered at the origin, and put Snuke there. Snuke will move to the hole with the smallest Euclidean distance from the point, and fall into that hole. If there are multiple such holes, the hole with the smallest index will be chosen.

For every i (1 \leq i \leq N), find the probability that Snuke falls into the i-th hole.

Here, the operation of randomly choosing a point from the interior of a circle of radius R is defined as follows:

  • Pick two real numbers x and y independently according to uniform distribution on [-R,R].
  • If x^2+y^2\leq R^2, the point (x,y) is chosen. Otherwise, repeat picking the real numbers x,y until the condition is met.

Constraints

  • 2 \leq N \leq 100
  • |x_i|,|y_i| \leq 10^6(1\leq i\leq N)
  • All given points are pairwise distinct.
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print N real numbers. The i-th real number must represent the probability that Snuke falls into the i-th hole.

The output will be judged correct when, for all output values, the absolute or relative error is at most 10^{-5}.

Sample Input 1

2
0 0
1 1

Sample Output 1

0.5
0.5

If Ringo put Snuke in the region x+y\leq 1, Snuke will fall into the first hole. The probability of this happening is very close to 0.5. Otherwise, Snuke will fall into the second hole, the probability of which happening is also very close to 0.5.

Sample Input 2

5
0 0
2 8
4 5
2 6
3 10

Sample Output 2

0.43160120892732328768
0.03480224363653196956
0.13880483535586193855
0.00000000000000000000
0.39479171208028279727