#P18219. The Wheel of Fortune

The Wheel of Fortune

The Wheel of Fortune

教皇和女祭司对宇宙的奥秘充满了好奇。为了探索地球——显然也是宇宙的一部分——上的一些奥秘,他们用一个奇怪的转盘研究重力对随机过程的影响。

转盘是一个凸多边形。把旋转中心与每个顶点相连,就把转盘分成若干个三角形区域,每个区域代表一种奖项。转动转盘后,停留在正下方的区域就是获奖区域。

无偏转盘的旋转中心位于质心,每个区域获奖的概率只与它占据的角度有关。不过,这里的转盘可能有偏:当旋转中心不在质心时,转盘最终总会使旋转中心指向质心的方向朝下,因此结果总落在这个方向对应的区域。

为了让转盘变得有趣,教皇决定在转盘内按面积均匀随机选择一个位置,放上一枚质量为 ww 的小磁铁。把磁铁看作一个质点,它会改变整个系统的质心,从而改变转盘的结果。转盘本身每单位面积的质量均匀为 11。

第一个样例中,不加磁铁的转盘,以及一种加入磁铁后改变结果的情况

女祭司想知道,经过上述扰动后,每个区域最终成为获奖区域的概率。

可以证明,不能唯一确定获奖区域的情况——旋转中心恰好在新质心上,或者新质心恰好位于区域边界上——发生的概率测度为 00,因此可以忽略这些情况。

输入格式

第一行包含两个整数 n,wn,w,分别表示转盘的顶点数量和磁铁质量。

接下来 nn 行,每行包含两个整数 xi,yix_i,y_i,表示第 ii 个顶点的坐标。顶点按照凸多边形边界的逆时针顺序给出。

最后一行包含两个整数 Ox,OyO_x,O_y,表示旋转中心的坐标。保证它严格位于原凸多边形内部。

顶点两两不同,但允许相邻三个顶点共线。若相邻顶点 uu、v=(u mod n)+1v=(u\bmod n)+1、t=(v mod n)+1t=(v\bmod n)+1 共线,则顶点 vv 严格位于顶点 uu 与顶点 tt 之间的线段上。也就是说,多边形所有内角均在 (0,π](0,\pi] 内。

输出格式

输出 nn 行。第 ii 行包含一个实数 pip_i,表示由旋转中心、第 ii 个顶点和第 (i mod n)+1(i\bmod n)+1 个顶点确定的三角形区域最终获奖的概率。

若答案的绝对误差或相对误差不超过 10−610^{-6},则认为答案正确。

数据范围

  • 3≤n≤1000003\le n\le100000;
  • 1≤w≤1091\le w\le10^9;
  • ∣xi∣,∣yi∣,∣Ox∣,∣Oy∣≤30000|x_i|,|y_i|,|O_x|,|O_y|\le30000;
  • 设原转盘面积为 SS,保证 max⁡{S/w,w/S}≤1000\max\{S/w,w/S\}\le1000。

样例 1

输入:

5 5
1 0
3 0
4 2
2 4
0 2
2 2

输出:

0.313777778
0.235555556
0.107555556
0.107555556
0.235555556

样例 2

输入:

8 8
0 0
1 0
2 0
2 1
2 2
1 2
0 2
0 1
1 1

输出:

0.125000000
0.125000000
0.125000000
0.125000000
0.125000000
0.125000000
0.125000000
0.125000000

样例 3

输入:

3 3
-1 -10
1 -10
0 1
0 0

输出:

1.000000000
0.000000000
0.000000000

样例 4

输入:

4 36000000
-30000 -30000
30000 -30000
30000 30000
-30000 30000
1 0

输出:

0.249998611
0.248327778
0.249998611
0.251675000

样例 5

输入:

4 2500
5 0
5 5
0 5
0 0
1 1

输出:

0.402977500
0.402977500
0.097022500
0.097022500