405916: GYM102156 G Battle Royale

Have you ever played Battle Royale games? In this kind of games, players are left alone and empty in a large area, and they must collect weapons, ammo, medkits and armor in order to kill each other. The game ends when only one player remains, this player is declared the winner.

To provoke players to fight each other, the safe zone is introduced. Players who are outside the safe zone are getting damage. Safe zone is always getting smaller and smaller, until it becomes a single point, so sooner or later each player has to make a choice: get inside a safe zone and fight other players or stay outside, lose hit points and eventually die.

In one-dimensional world, there is a famous Battle Royale game: BattleUnknown's Playergrounds. The game area is a segment $$$[L, R]$$$. Initially, the safe zone is the whole segment $$$[L, R]$$$, and in the end of the game it will narrow to a single point $$$M$$$ ($$$L \le M \le R$$$), where $$$M$$$ is chosen equiprobably on the segment $$$[L, R]$$$. The safe zone narrows in such a way that $$$\frac{M-L}{R-M} = const$$$, and each second its length decreases by 1.

Today we got a match between $$$n$$$ extremely passive players: the $$$i$$$-th of them is hiding in the house with the coordinate $$$x_i$$$ and is not going to move. Imagine it, they better die outside the safe zone than move out of their houses! Their plan is to outlive all others using the medkits they have collected: the $$$i$$$-th player can stay alive for $$$a_i$$$ seconds outside the safe zone.

For each player, determine the probability that this player wins the game.

The first line contains three integers $$$n$$$, $$$L$$$ and $$$R$$$: the number of players and the endpoints of the game segment ($$$1 \le n \le 10^{5}$$$, $$$-10^{6} \le L < R \le 10^{6}$$$).

The next line contains $$$n$$$ integers $$$x_i$$$: coordinates of the houses where players hide ($$$L < x_i < R$$$). They are all different and sorted in ascending order.

The next line contains $$$n$$$ integers $$$a_i$$$: the time $$$i$$$-th player can stay alive outside the safe zone ($$$0 \le a_i \le 10^{6}$$$).

Output $$$n$$$ lines. The $$$i$$$-th line should contain a single real number: the probability that the $$$i$$$-th player wins the game. The absolute error of each number should not exceed $$$10^{-9}$$$.

2 -5 5
-1 1
3 5

0.438447187191170
0.561552812808830

2 0 10
5 7
5 2

1.000000000000000
0.000000000000000

3 0 10
3 4 7
3 4 8

0.109584240176570
0.121686455414586
0.768729304408844