410328: GYM104009 L Transafagarasan

Transfagarasan is finally open to be driven through. To go down the mountain, travellers have to go through a serpentine road with $$$N(1 \leq N \leq 10^5)$$$ turns. The road has a starting height $$$y_s$$$ and a lower, end height $$$y_f$$$. Note that $$$0 \leq |y_s|, |y_f| \leq 10^9$$$, and that you go down the mountain, meaning that $$$y_s > y_f$$$.

The road is laid out such that, on one hand, turn number $$$i$$$ (where $$$i$$$ is an odd integer), requires drivers to turn to the left (from the driver's perspective). On the other hand, turn number $$$i$$$ (where $$$i$$$ is an even integer) requires drivers to turn to the right (from the driver's perspective).

Formally, you can imagine these $$$N$$$ turns as circles, where circle $$$i$$$ has radius $$$r_i$$$ ($$$1 \leq r_i \leq 10$$$) and a centre $$$(x_i, y_i)$$$, where it holds that $$$0 \leq |x_i|, |y_i| \leq 10^9$$$, and the road moves around these circles. It is guaranteed that circle $$$i$$$ is strictly above circle $$$i+1$$$ - in other words, $$$y_i-r_i > y_{i+1}+r_{i+1}$$$. Plus, it is also guaranteed that if $$$i$$$ is an odd number, then circle $$$i$$$ is to the left of circle $$$i+1$$$ (i.e. $$$x_i+r_i < x_{i+1}-y_{i+1}$$$), and if $$$i$$$ is an even number, then circle $$$i$$$ is to the right of circle $$$i+1$$$ (i.e. $$$x_i-r_i > x_{i+1}+y_{i+1}$$$).

Last but not least, note that the first circle is going to be below the starting height: in other words, $$$y_s \ge r_1+y_1$$$. Similarly, the last circle is going to be above the finishing height, meaning that $$$y_f \le y_n-r_n$$$.

What is the minimum distance $$$D$$$ of the road given that it starts anywhere at the starting height $$$y_s$$$, it ends anywhere at the ending height $$$y_f$$$, and it moves around the given circles as described above?

A picture containing of how such a road would look like can be seen on the second page of the problem statement, after the example section. Please note that the picture does NOT match the numerical example and it is meant as a visual representation of the restrictions in the problem.

Note that $$$D$$$ must have a precision of at least $$$10^{-7}$$$ in order to be considered correct.

The first line of input will contain three integers: $$$N$$$ ($$$1 \leq N \leq 10^5$$$), $$$y_s$$$ ($$$0 \leq |y_s| \leq 10^9$$$), $$$y_f$$$ ($$$0 \leq |y_f| \leq 10^9$$$). $$$N$$$ represents the number of circles, $$$y_s$$$, the starting height, and $$$y_f$$$, the end height.

The next $$$N$$$ lines of input will contain three integers $$$x_i$$$ $$$(0 \leq |x_i| \leq 10^9)$$$, $$$y_i$$$ $$$(0 \leq |y_i| \leq 10^9)$$$ and $$$r_i$$$ ($$$1 \leq r_i \leq 10$$$).

Print the distance $$$D$$$ - the minimum distance that a driver must travel to get from $$$y_s$$$ to $$$y_f$$$. Note that $$$D$$$ must be printed with a precision of at least $$$10^{-7}$$$.

3 8 0
1 7 1
4 4 1
1 1 1

14.5884381