GETFAST - Getting There Fast
Original statement in spanish at http://www.dc.uba.ar/events/icpc/download/problems/taip2011-problems.pdf
Gabriela drives a school bus. Being one of the few women who have that job, she is always mocked by the male drivers. To improve her status, she decided that besides driving responsibly she is going to drive more efficiently. Her idea is to finish her route spending as little time as possible, without violating any traffic rule.
The bus Gabriela drives has a very modern driving system that allows her to adjust the acceleration to any real number instantly. Hence, the acceleration is constant by intervals, jumping to another acceleration whenever Gabriela decides so. If v is the bus' speed at a given instant of time, and a its acceleration that remains constant over a period of time t, then the speed at the end of that period will be v + at. Moreover, the bus will move a distance of at2/2 + vt during that period of time.
The traffic rules prevent vehicles from using an acceleration greater than A, or a deceleration less than D, i.e. the acceleration a at any time must satisfy -D <= a <= A. Moreover, there are check points along the route of the bus where the speed must lie within a certain given interval.
Gabriela knows in advance the location of the check points, the total length of the route, and the constants A and D. At the beginning of the route the speed and acceleration of the bus are both 0. There are no additional restrictions regarding the speed or the acceleration the bus must have at the end of the route (in particular, it is not necessary to stop in the end). Your job is to use this data to determine the minimum time that Gabriela needs in order to finish the route without violating the rules.
The input contains several test cases. Each test case is described using several lines. The first line of each test case contains four integers N, L, A and D. N represents the total number of check points that are present in Gabriela's route (1 <= N <= 105). L indicates the length of the route in meters (2 <= L <= 107). A and D represent, respectively, the maximum allowed acceleration and deceleration for the bus (1 <= A, D <= 100). Each of the following N lines describe a different check point using three integers X, V and W that represent, respectively, the distance between the check point and the starting point of the route (1 <= X <= L-1), the minimum speed, and the maximum speed allowed for the bus at the time it passes by that check point (1 <= V, W <= 100). Assume that in each test case the check points are given in ascending order of distance from the start point of the route, and no two check points are at the same distance from the start point. In this problem, the length is expressed in m (meters), the speed in m/s, and the acceleration in m/s2. The end of the input is indicated by a line containing the number -1 four times, and should not be processed as a test case.
For each test case, output a single line containing a rational that represents the minimum time (in seconds) needed for Gabriela to finish her route without violating any traffic rule, or an asterisk if it is impossible to do that. Round the answer to the nearest rational with two decimal digits. In case of a tie, round up. Print exactly two digits after the decimal point, even if that means ending the number with 0's.
1 40 10 1 20 21 21 1 40 10 5 20 20 20 1 20 10 50 10 14 15 5 1000 2 5 400 30 80 600 35 50 700 10 30 900 30 40 950 10 30 -1 -1 -1 -1
* 2.83 2.00 35.96