Chain-Confined Path#3770
There is a chain consisting of several circles on a plane. The first (and last) circle in the chain intersects only with its next (previous) circle, and each intermediate circle intersects only with its two neighboring circles.
Your task is to find the shortest path satisfying the following conditions:
The path connects the centers of the first and last circles.
The path remains within the chain, that is, all the points on the path lie inside or on at least one of the circles.
Figure 1 shows an example of such a chain and the corresponding shortest path.
Figure 1: An example chain and the corresponding shortest path
The input consists of multiple datasets. Each dataset describes the circles in the chain in the following format:
The first line contains an integer (3 \leq n \leq 100) — the number of circles. Each of the following lines contains three integers x_i, y_i, and r_i, separated by spaces, describing the coordinates of the center and the radius of the -th circle C_i. You can assume that 0 \leq x_i \leq 1000, 0 \leq y_i \leq 1000, and 1 \leq r_i \leq 25.
It is guaranteed that C_i and C_{i+1} (1 \leq i \leq n-1) intersect at two distinct points. For j \geq i+2, the circles C_i and C_j are disjoint and neither contains the other. Furthermore, no circle contains the center of any other circle.
The end of input is indicated by a line containing a single zero.
Figure 1 corresponds to the first dataset of the sample input below. Figure 2 shows the shortest paths for the following datasets.
Figure 2: More example chains and the shortest paths
For each dataset, output a single line containing the length of the shortest chain-confined path between the centers of the first and last circles. The answer must not have an error greater than . No extra characters should appear in the output.
Example 1