Robot#471
Robot needs to travel on a plane from point to point . Moving in a straight line is not always possible because of obstacles. You need to write a program that calculates the minimum path length of the robot from point to point . Let us consider the size of the robot negligibly small compared to the distances and obstacle sizes. All obstacles are represented as a set of segments on the plane. The robot cannot cross the interior points of these segments, but it can pass through the ends of the segments or move along a segment.
The first line contains an integer — the number of obstacle segments (0 \leq N \leq 100). The next lines each contain four integers X_1, Y_1, X_2 and Y_2, which are the coordinates of the endpoints of each segment. The last two lines contain the and coordinates of points and . It is guaranteed that all coordinates do not exceed in absolute value, and none of the segment endpoints coincide with any other endpoint. The starting and ending points of the path are different and do not belong to any segment.
Print one number — the length of the shortest path from point to point with four digits after the decimal point. If the required path does not exist, print –1.
Example 1