Regatta of Scientists
By Alessandro Luna de Almeida, UFPE 
By Alessandro Luna de Almeida, UFPE
Every year since 1996, computer scientists worldwide meet for the famous Regatta of Scientists. The competition consists of a boat race with obstacles along the ocean, where the goal of each team is, from a common point, reach the point of arrival without any obstacle being touched or passed over. A team that touches or passes over an obstacle is automatically disqualified. The winning team is the one who first reaches the end point (the point of arrival is different from the starting point).
You have been hired by the Brazilian team to develop a program that calculates the length of the shortest valid route from the point of departure to the point of arrival. The ocean is considered an infinite plane, where each obstacle is located in a fixed position and is represented by a line segment described by its two ends (x1, y1) and (x2, y2). The boats are dimensionless (represented as a point in the plane) and obstacles have negligible thickness.
The obstacles are arranged such that they do not intersect. Similarly, the start and arrival points of the competition are not intercepted by any obstacle.
The input consists of several test cases. The first line of a test case contains five integers xi, yi, xf, yf and n, representing respectively the coordinates of the starting point (xi, yi), the coordinates of the arrival point (xf, yf) and the number of obstacles (n ≤ 150). Each of the next n lines of a test case contains four integers x1, y1, x2 and y2 coordinates that describe the two extremes of an obstacle. Assume that x and y coordinates of any point satisfies -5000 ≤ x, y ≤ 5000. The end of input is represented by a line containing xi = yi = xf = yf = n = 0.
For each test case, print a line containing the length of the shortest valid route possible, with 2 digits after the decimal point.
| Sample Input | Sample Output |
|
0 0 10 0 1 |
10.20 |