408102: GYM102985 I Sharing Cereal II

After giving out many of his Cheerio boxes, Lang realizes he still has $$$n$$$ cereal boxes left. Feeling great about his philanthropic endeavors, he now decides to play with his cereal boxes. Lang decides to line up his boxes in a straight line (let this line be the x-axis), with each cereal box being located at some $$$(x_i, 0)$$$. Furthermore, Lang's cereal boxes each have an individual height of $$$h_i$$$ as well.

Looking at the cereal boxes, Lang quickly uses his mastery of physics to calculate the exact probability $$$p_i$$$ that when tapped that the box will fall left. As such, the $$$i^{th}$$$ cereal box would also fall right with probability $$$1 - p_i$$$. Note that since some cereal boxes, when they fall over, would actually cause a chain reaction, and knock down more boxes, which could then go on to knock down more boxes. Specifically, if a box has height $$$h$$$, then any box within a distance of $$$h$$$ or less and in the same direction that the original box fell in would also fall in that direction. These boxes can continue to cause more boxes to fall.

Lang himself is interested in the minimum number of taps it will take for all the boxes to one side of his current direction, namely $$$(0, 0)$$$, to fall. Since he has a very large number of boxes, this task proves to very difficult for him. As such, he decides to utilize a heuristic to weight his choice with regards to the probability of the boxes on two ends of his current position falling outwards. Specifically, if at a certain point, if the next box on the left has a probability $$$p_i$$$ of falling left, and the next box on the right has a probability $$$p_j$$$ of falling left, then he will choose the book on the left with probability $$$\frac{p_i}{p_i + (1 - p_j)}$$$.

While this heuristic is clearly suboptimal, it does make Lang's actions strictly probabilistic. Given this information, determine the probability that Lang will knock over all Cheerio boxes to his left before all his Cheerio boxes on the right. If it happens to be that after a tap, the leftmost box and the rightmost box both fall without any additional taps, this will still count.

The first line of the input is a single integer, $$$n (1 \le n \le 10^3)$$$, the number of boxes.

The next $$$n$$$ lines of input each contain 2 integers $$$x_i (-10^8 \le x_i \le 10^8)$$$ and $$$h_i (1 \le h \le 10^5)$$$ followed by a real number $$$p_i (0 \le p \le 1.0)$$$, where $$$x_i$$$ is the coordinate the box is at on the x-axis, $$$h_i$$$ is the height of the box, and $$$p_i$$$ is the probability that the box falls left.

It is guaranteed there is at least one box to both the left and the right of where Lang starts and that there is no box where Lang starts.

A single real number, the probability that all cereal boxes on the left fall before the ones on the right, or if they all fall after the same tap.

The answer will be judged as correct if it has absolute or relative error at most $$$10^{-4}$$$.

4
-4 2 0.75
-2 2 0.75
2 2 0.5
4 2 0.5

0.6660000000999999

Calculation for sample testcase detailed below, with overall success rate of each path in parenthesis.

Pick left, fall left: $$$0.6 \cdot 0.75 (0.45)$$$

Pick left, fall right: $$$0.6 \cdot 0.25$$$

• Pick left: $$$0.6 (0.09)$$$
• Pick right, fall left, pick left: $$$0.4 \cdot 0.5 \cdot 0.6 (0.018)$$$

Pick right, fall left, pick left: $$$0.4 \cdot 0.5 \cdot 0.6$$$

• Fall left: $$$0.75 (0.09)$$$
• Fall right, pick left: $$$0.25 \cdot 0.6 (0.018)$$$

Overall chance: $$$0.45 + 0.09 + 0.018 + 0.09 + 0.018 = 0.666$$$