National University of Singapore

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