Lap time
A car’s line on a ring track is a closed polyline of n points P1, …, Pn, listed in the direction of travel; after Pn comes P1 again. The car is limited by three rules.
- Corners. The speed at point Pi is at most √(a·Ri), where Ri is the radius of the circle through Pi−1, Pi, Pi+1, and at most V. If the three points lie on one line, the only limit is V.
- Acceleration. If di is the length of the segment from Pi to Pi+1 and vi the speed at Pi, then vi+12 ≤ vi2 + 2b·di.
- Braking. vi2 ≤ vi+12 + 2c·di.
The car goes lap after lap, and at each point its speed is the largest that all three rules allow (such a set of speeds is unique). It covers the segment from Pi to Pi+1 in 2di / (vi + vi+1) seconds. How long is a lap?
Input
The first line holds n, a, b, c, V (3 ≤ n ≤ 200,000; a, b, c are accelerations in m/s², from 0.1 to 100; V is the top speed in m/s, from 1 to 1000; the numbers may be fractional). Then come n lines with the coordinates of the points in metres, at most 105 in absolute value. Neighbouring points do not coincide.
Output
The lap time in seconds. The answer is accepted if its relative error is at most 10−6.
Examples
Example 1
4 10 5 10 100 0 0 100 0 100 50 0 50
12.688455161
Example 2
14 12 4 9 60 0 0 50 0 100 0 150 0 200 0 220 20 220 40 200 60 150 60 100 60 50 60 0 60 -20 40 -20 20
19.362116936
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
First compute for each point its “ceiling” from the corner: the radius of the circle through three points equals the product of the lengths of the triangle’s three sides divided by four times its area, that is, by 2·|cross product|. Without the acceleration and braking rules the answer would be the sum of the segment times at these speeds. What do the other two rules change?
2Hint 2
If you go round the ring forward, limiting the speed by acceleration, and then backward, limiting it by braking, you get almost the answer. But where to start, if the ring is closed and the speed at the start is unknown? There is one point where the speed is known for certain.
3The idea
Call a set of speeds that satisfies all the rules feasible. If two sets are feasible, so is their pointwise maximum: for example, max(ui+1, wi+1)2 ≤ max(ui2, wi2) + 2b·di. So the largest feasible set exists and is unique: these are the car’s speeds.
Let s be the point with the lowest ceiling Ls. The set “speed Ls everywhere” is feasible: it is not above any ceiling, and acceleration and braking at a constant speed demand nothing. So in the largest set the speed at every point is at least Ls, and at s itself exactly Ls. That is the point where the speed is known.
Then two passes from s. Forward: vi = min(Li, √(vi−12 + 2b·di−1)). Backward: vi = min(vi, √(vi+12 + 2c·di)). Any feasible set is not above the result: this is checked by induction along each pass, starting from s, where a feasible speed is at most Ls. And the result itself is feasible: the backward pass lowers the speed only where the speed ahead is lower, and there the acceleration rule holds by itself; nothing breaks at the joint at point s, because all the speeds are at least Ls.
4Walkthrough
Compute the segment lengths and the ceilings, find the point with the lowest ceiling, make a forward pass and a backward pass round the ring, and add up the times 2di / (vi + vi+1). If three points are on one line, the cross product is zero, and the ceiling is just V.
The sixth and seventh tests are the ring of the Sokol circuit and the car from the article: along the centre line of the road a lap lasts 100.363 seconds, along the line found by the listing’s genetic algorithm 100.352. This is exactly the function the genetic algorithm calls thousands of times.
4+Solution
5Complexity
O(n): two passes round the ring and one over the segments.
6Common mistakes
- Starting from the first point. The speed there is not known in advance: if a tight corner follows it and the end of a straight precedes it, passes started from it do not account for braking across the joint of the lap. The fifth and eighth tests are built so that the slow corner falls right on the joint.
- Only the forward pass. Then the car flies into a corner at full speed and brakes instantly; the lap comes out shorter than the real one.
- Division by zero on straight sections, where three points are on one line.
- Mixed-up pairs of neighbouring points. In the acceleration rule di is the segment to point i + 1, while the forward pass to point i needs the segment from i − 1; it is easy to mix up the index, and on an uneven polyline this changes the answer.