Scientists' Regatta

Every year since 1996, computer scientists from all over the world gather for the famous Scientists' Regatta. The competition is a boat race with obstacles on the ocean. All teams start from a common point, and each team must reach the finish point without touching or crossing any obstacle. A team that touches or crosses an obstacle is disqualified immediately. The winning team is the first one to reach the finish point. The finish point is different from the starting point.

The Brazilian team has hired you to write a program that computes the length of the shortest valid route from the starting point to the finish point.

The ocean is an infinite plane. Each obstacle is at a fixed position and is a line segment given by its two endpoints $(x_1, y_1)$ and $(x_2, y_2)$. Boats have no size (each boat is a point in the plane), and obstacles have negligible thickness.

No two obstacles intersect. Likewise, neither the starting point nor the finish point lies on any obstacle.

A boat can pass as close to an obstacle as it wants. So the value to compute is the infimum of the lengths of valid routes. It equals the shortest distance computed as if a route may pass through obstacle endpoints and run along obstacles. A route still may not cross the interior of an obstacle.

The input contains several test cases. The first line of each test case contains five integers $x_i$, $y_i$, $x_f$, $y_f$, and $n$: the coordinates of the starting point $(x_i, y_i)$, the coordinates of the finish point $(x_f, y_f)$, and the number of obstacles $n$ $(0 \le n \le 150)$. Each of the next $n$ lines contains four integers $x_1$, $y_1$, $x_2$, and $y_2$, the coordinates of the two endpoints of one obstacle. The coordinates $x$ and $y$ of every point satisfy $-5000 \le x, y \le 5000$.

A line with $x_i = y_i = x_f = y_f = n = 0$ marks the end of the input.

For each test case, print one line with the length of the shortest valid route, rounded to two decimal places. Always print exactly two digits after the decimal point.