Problem A
Airport Logistics


Many airports have moving conveyor belts in the corridors between halls and terminals. Instead of walking on the floor, passengers can choose to stand on a conveyor or, even better, walk on a conveyor to get to the end of the corridor much faster.

The brand new Delft City Airport uses a similar system. However, in line with the latest fashion in airport architecture, there are no corridors: the entire airport is one big hall with a bunch of conveyor lines laid out on the floor arbitrarily.

To get from a certain point $A$ to a certain point $B$, a passenger can use any combination of walking on the floor and walking on conveyors. Passengers can hop on or off a conveyor at any point along the conveyor. It is also possible to cross a conveyor without actually standing on it.

Walking on the floor goes at a speed of $1$ meter/second.
Walking forward on a conveyor goes at a total speed of $2$ meter/second.
Walking in reverse direction on a conveyor is useless and illegal, but you may walk on the floor immediately next to the conveyor. (Conveyors are infinitely thin.)

How fast can you get from $A$ to $B$?


The first line contains four floating point numbers, $X_ A$, $Y_ A$, $X_ B$, and $Y_ B$. They describe the coordinates of your initial location $A = (X_ A,Y_ A)$ and your final location $B = (X_ B,Y_ B)$.

The second line contains an integer $N$, the number of conveyors in the hall ($0 \leq N \leq 100$). The following $N$ lines each contain four floating point numbers, $X_1$, $Y_1$, $X_2$, and $Y_2$, describing a conveyor which starts at the point $(X_1,Y_1)$ and ends at the point $(X_2,Y_2)$, running in a straight line from start to end.

All coordinates are floating point numbers in the range ($0 \leq X, Y \leq 1000.0$), expressed in units of meters, given with at most $6$ decimals after the decimal point.

Conveyors are at least $1$ meter long. Conveyors do not intersect or touch. Your start and destination are not on any conveyor.


Write one line with a floating point number, the minimum time (in seconds) needed to get from $A$ to $B$ in seconds.

Your answer may have an absolute error of at most $10^{-4}$.

Sample Input 1 Sample Output 1
60.0 0.0 50.0 170.0
40.0 0.0 0.0 0.0
5.0 20.0 5.0 170.0
95.0 0.0 95.0 80.0
Sample Input 2 Sample Output 2
60.0 0.0 50.0 170.0
40.0 0.0 0.0 0.0
5.0 20.0 5.0 170.0
95.0 0.0 95.0 100.0
Sample Input 3 Sample Output 3
0.0 1.0 4.0 1.0
0.0 0.0 4.0 0.0
Sample Input 4 Sample Output 4
0.0 1.0 10.0 1.0
1.0 0.0 2.0 3.0
6.0 1.0 4.0 1.0

Please log in to submit a solution to this problem

Log in