Jogging
Time limit1sMemory limit512 MB
Given N pairs of one-way moving walkway lines in the plane with boarding and leaving costs, find the minimum travel time from house to office where walking off-line is allowed.
- Level
Hard8 of 10
- Topics
- Shortest path, Geometry, Graph, Math
- Solved
- No attempts yet
Problem
It is Sunday, November 1, 2390, and Eddy has just been elected to the World Council. The work is interesting and carries real responsibility, and Eddy wants to throw himself into it, but there is a problem. Eddy loves sport. He likes jogging most of all, and since he was a little boy he has jogged at least thirty minutes every single day. As a councillor he will have even less free time than he had as a teacher. Where will the time for jogging come from?
Eddy decided to jog on his way to work. The Council building is far from his house, so he wants to combine jogging with public transport. Moving pathways are the only public transport in the Capital. One line of pathways is a pair of straight pathways running in opposite directions at the same speed . The pathways are very long and narrow, so this problem treats each pair as one infinite straight line in the plane. Every line also comes with two numbers and , the time needed to board that line and the time needed to leave it. Crossing a pathway on foot costs no extra time. Changing from line to line at the point where the two meet takes exactly seconds. The two lines do not really intersect there, because special bridges are built at those points.
Eddy wants to jog on the pathways as well, so on a pathway he moves with ground speed , where is his speed when jogging on still ground.
Find the smallest travel time from Eddy's house to the Council building. A route is made of several straight segments, and some of them can lie on one of the existing pathways.
Input
The first line contains one integer , the number of pairs of moving pathways in the city ().
The second line contains six real numbers , , , , , separated by spaces: the coordinates of Eddy's house, the coordinates of the Council building, the speed of the pathways, and Eddy's own speed.
Each of the next lines describes one line of pathways with six real numbers , , , , , . The points and are two different points on that line, and and are the boarding and the leaving time ().
No coordinate exceeds in absolute value, and and are real numbers between and . All pathways lie on different straight lines. Neither nor lies on any pathway.
Output
Print the smallest travel time from the house to the Council building, rounded to six digits after the decimal point, with all six digits written out.