beecrowd | 1223

Toboggan of Marbles

Maratona de Programação da SBC Brazil

Timelimit: 1

A factory wants to produce a toboggan of marbles toy (marble run) as shown in the following figure, consisting of two vertical rods of wood, which support small rigid flaps connected to the rods. The flaps are connected to the left and right rods in an alternate fashion. A small marble ball is dropped on the highest flap of the marble run, and under the effect of gravity the marble slides by the flaps, eventually leaving the toy.

The design of the toy, containing the specifications of its size, position and tilt of each flap, was made by the factory owner. Thousands of units are already being made in China, and the factory manager has been asked to buy the marbles. Before placing the order for thousands of marbles, however, he wants to know the maximum diameter of the marble so it does not get stuck in the middle of the toy.

Figure 1: Two examples: (a) the marble reaches the end, and (b) the marble gets stuck in the middle of the toy.

The factory manager wants you to write a program that, given the toy specifications, determines the maximum diameter of the marble so that it does not get stuck in the middle of the toy.


The input contains several test cases. The first line of a test case contains an integer N (1 ≤ N ≤ 103) indicating the number of flaps of the toy. The second line contains two integers L (1 ≤ L ≤ 103) and H (1 ≤ H ≤ 103), indicating respectively the distance between the rods and the height of the rods. The left rod is at position 0 of the coordinate axis X, so that the right rod is at position L of the X axis.

Each of the following N lines describes a flap. Flaps are described from highest to lowest, alternately in relation to the rod to which the flap is attached. The highest flap (the first to be described) has an end connected to the left rod and the second highest flap (the second to be described) has one end connected to the right rod, and so forth. Odd flaps are connected to the left stem, the even flaps are connected to the right rod.

Each flap is described in a line containing three integers Yi, Xf (0 < Xf < L) and Yf (0 ≤ YfH). (Xf , Yf) indicates the coordinate of the flap’s end (the not connected end). The coordinate of the connected end of an odd flap is (0, Yi (0 ≤ YiH)), and the coordinate of the connected end of an even flap is (L, Yi ).

For all flaps Yi > Yf (ie, there is a slope between the start and the end of a flap), and the length of the flap is less than the width of the toy. Moreover, for two consecutive flaps A and B, Yfa >= YiB (ie, the end of flap Ahas height greater than or equal than the beginning of flap B).

Consider that the flaps are very thin, so that its thickness can be neglected.


For each test case print a line containing a single number, with exactly two decimal places, indicating the largest diameter of a marble so it that it can reach the end of the toy.

Sample Input Sample Output

6 10
9 3 8
6 2 5
4 3 1
5 10
9 3 7
7 2 4
2 3 0