Eco-driving#6831
My colleague Elisabeth is lazy, both at work and when going to work. She never wants to do more than necessary, which also applies to her journey to work. Her goal is to use a minimum amount of energy, which she achieves by braking and accelerating as little as possible. This method applies to all wheel-based transport means she owns.
Elisabeth has earlier optimized her route by trial and error, but now wants your help to find the optimal path. She has provided a map with junctions and straight one-way roads between the junctions. If a road is dual way, it is represented as two one way roads.
Fortunately, Elisabeth often works night shifts, so braking and acceleration are only needed when turning in a junction, as there is no other traffic on the roads. Her goal is to find a route where the maximum turning angle in the junctions is minimized, as this means maximized speed. However, the route can not be too long.
The first line contains three space separated integers (2 \leq j \leq 200), (1 \leq r \leq 39800) and (1 \leq d \leq 1000000). is the number of junctions, is the number of one way roads which are connecting two junctions, and is the maximum distance, in meters, that Elisabeth wants to travel. The road network is such that there is no path, that Elisabeth may want to use, which has the length such that d < l < d \cdot (1 + 10^{-6}).
Then follow lines with two integers and (-100000 \leq x, y \leq 100000), the distinct coordinates in meters on a flat ground. Elisabeth lives at junction and her work is at junction . After that lines follow with two integers and . This should be interpreted as the one way road between the one-indexed source and destination junctions and (1 \leq a, b \leq j).
Output one line with the maximum turning angle of the route, minimizing the maximum turning angle as much as possible. The turning angle must be output in degrees and have an absolute or relative error at most 10^{-6}. If there is no such route that is short enough, output "Impossible" on a single line.
Example 1
Example 2