Robotic Rails

Time limit10sMemory limit128 MB

Summary

Given up to 100 line segments in the plane, find the shortest path from a fixed start point and heading to a fixed target point and heading, where turns at intersections may not exceed 90 degrees.

Level: Hard8 of 10
Topics: Graph, Geometry, Shortest path, Implementation
Solved: No attempts yet

Problem

Karel is a mechanical robot standing in a very large hall. It moves along a system of rails built into the floor. Every rail is a straight segment so narrow that its width can be treated as zero, and rails may intersect one another or even overlap.

Karel can switch from one rail to another at any point the two rails have in common. Because of technical limits, however, at any single point Karel may never turn by more than 90 degrees: every bend of its path must be a right angle or wider (an obtuse angle). A sharper turn is impossible, so at some crossings Karel cannot turn directly and must take a longer way around instead.

Your task is to compute the length of the shortest path that lets Karel travel from its start position to the required target position.

Input

The input consists of several test scenarios.

Each scenario begins with a line containing a single positive integer $R$ ( $1 \le R \le 100$ ), the number of rail segments. Each of the next $R$ lines contains four integers $x_1$ , $y_1$ , $x_2$ , $y_2$ , the coordinates of the two endpoints of one segment. Every coordinate is between $-10000$ and $10000$ , and every segment has non-zero length.

The last scenario is followed by a line containing a single zero.

Karel always starts at the first point of the first segment (the start of that segment) and initially faces along that first segment. Therefore its first move must go in that direction, or deviate from it by at most 90 degrees.

The target is the last point given in the scenario (the end of the last segment); it is always different from the start. Karel must not only reach the target but also stop facing the direction of the last segment. It may arrive along that last segment, or along a different segment as long as its direction deviates from the last segment's direction by at most 90 degrees.

Output

For each scenario, output a single line with the length of the shortest path that satisfies all of the rules above, rounded to exactly three digits after the decimal point (trailing zeros may appear). If the target cannot be reached at all, output the word unreachable instead.

Examples3

Example 1

Input

Expected output

9.541
unreachable

Example 2
Input
```
1
0 0 3 4
0
```
Expected output
```
5.000
```
Example 3
Input
```
2
0 0 2 0
2 0 2 2
0
```
Expected output
```
4.000
```