Peter was supposed to catch a morning train at 7:30. But as usual, he overslept the alarm set to 6:30 and he just woke up with 7:29 on the clock. He only managed a single “Oh crap!” before the train was gone. Luckily for Peter, everything can still be saved. He can take his old car out of the garage and drive it to his destination.
Peter lives in the middle of an abandoned countryside. There is a single long straight road going across the countryside. Peter’s home and his destination both lie on this road.
Still, Peter has a valid reason to prefer the train. The whole countryside is covered by train tracks, and thus the road is riddled with railroad crossings. And as trains have priority over cars, you could easily end up waiting for a long time at some of those crossings.
Moreover, even if you are not waiting for a train to pass, you still need to approach the railroad crossings carefully – they are in pretty bad shape and if Peter were to drive carelessly, the crossing could easily break his old car.
For the purpose of this task, the road is an inﬁnite straight line. Peter’s home, his destination, each of the railroad crossings, and Peter’s car should all be considered points. Peter’s car is the only point that will be moving, all the other ones are stationary. The movement of Peter’s car is continuous (not discrete).
We will be using a linear coordinate system on the road, with Peter’s home being at 0 and his destination at some xend > 0. All coordinates are in meters, all speeds are in meters per second, all accelerations are in meters per second squared.
All the railroad crossings lie strictly between Peter’s home and his destination, at pairwise diﬀerent coordinates xi. In the input, their descriptions are ordered by their coordinate.
There are no other cars on the road. Peter’s car can move freely along the line, including the parts that are not between his home and his destination. However, the movement of his car is subject to the following constraints:
However, the railroad crossings are special: The maximum allowed speed at a railroad crossing is vmax (an integer).
But even when driving slower than vmax, the bumping while crossing the railroad sometimes tends to resonate parts of Peter’s car and Peter fears that the car might break. He has already tested that this does not happen if the speed of his car is an integer less than or equal to vmax. He now refuses to drive over a railroad crossing using any other speed.
Therefore, whenever the car crosses a railroad, its speed at that moment has to be a positive integer.
(Note that zero is not allowed. Stopping at a railroad crossing is forbidden by law.)
Peter’s car starts stationary (v = 0) at his home. Calculate the shortest time in which it is possible to park the car (i.e., have v = 0 again) at Peter’s destination (xend).
The ﬁrst line of the input ﬁle contains an integer t ≤ 500 specifying the number of test cases. Each test case is preceded by a blank line.
Each test case starts with a single line containing four numbers:
Next n lines describe railroad crossings, one per line. Each line starts with two numbers. The ﬁrst one a ﬂoating-point number xi: the coordinate of this crossing. The second one is a nonnegative integer mi: the number of trains that will be passing through the crossing. Then, 2mi ﬂoating-point numbers follow: for each train the start si,j and the end ei,j of the time interval when the crossing is blocked by the train.
You may assume the following things about the crossings:
There should be no numerically unstable test cases in the test data. More precisely, for each test case we used: 1) if we make small changes to the values si,j and ei,j, the optimal path remains essentially the same; and 2) if we make a small change to amax, the optimal path remains essentially the same.
In the easy subproblem M1, 0 ≤ n ≤ 1 (i.e., there is at most one crossing) and 0 ≤ mi ≤ 2 (there are at most two trains per crossing). In the hard subproblem M2, 0 ≤ n ≤ 30 and 0 ≤ mi ≤ 25.
For each test case, output a single line with a ﬂoating-point number on it – the earliest time Peter can be parked (v = 0) at position xend. Output suﬃciently many decimal places. Answers with absolute or relative error up to 10−6 will be accepted.
In the ﬁrst case, there is no crossing and so Peter may drive directly to his destination. The optimal strategy is to accelerate until he reaches x = 5, and then to brake for the rest of the way. Note that his maximum speed during this trip will exceed vmax.
In the second case the train will leave the crossing before Peter can possibly reach it. Still, the crossing limits the car speed. In the optimal solution Peter will cross the railroad crossing having speed v = 3.