Internet Problem Solving Contest

IPSC 2013

Problem M – Morning hassle

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.

Problem specification

For the purpose of this task, the road is an infinite 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 different 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:

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).

Input specification

The first line of the input file 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 first one a floating-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 floating-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.

Subproblem-specific constraints

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.

Output specification

For each test case, output a single line with a floating-point number on it – the earliest time Peter can be parked (v = 0) at position xend. Output sufficiently many decimal places. Answers with absolute or relative error up to 106 will be accepted.



10 1 3 0

10 1 30 1
5 1 2 3

In the first 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.