prithivMLmods/Coder-Stat

1 2<h1>Chain-Confined Path</h1>3<!-- end en only -->4 5 6<!-- begin en only -->7<p>8There is a chain consisting of multiple circles on a plane.9The first (last) circle of the chain only intersects with the next (previous) circle,10and each intermediate circle intersects only with the two neighboring circles.11</p>12<!-- end en only -->13 14<!-- begin en only -->15<p>16Your task is to find the shortest path that satisfies the following conditions.17<ul>18<li>The path connects the centers of the first circle and the last circle.</li>19<li>The path is confined in the chain, that is, all the points on the path are located within or on at least one of the circles.</li>20</ul>21Figure E-1 shows an example of such a chain and the corresponding shortest path.22</p>23<!-- end en only -->24 25<center>26<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_1183_1"><br><br>27<!-- begin en only -->28Figure E-1: An  example chain and the corresponding shortest path<br>29<!-- end en only -->30</center>31 32 33 34<h3>Input</h3>35 36 37<!-- begin en only -->38<p>39The input consists of multiple datasets.40Each dataset represents the shape of a chain in the following format.41</p>42<!-- end en only -->43 44<blockquote>45<i>n</i><br>46<i>x</i><sub>1</sub> <i>y</i><sub>1</sub> <i>r</i><sub>1</sub> <br>47<i>x</i><sub>2</sub> <i>y</i><sub>2</sub> <i>r</i><sub>2</sub> <br>48...<br>49<i>x</i><sub><i>n</i></sub> <i>y</i><sub><i>n</i></sub> <i>r</i><sub><i>n</i></sub> <br>50</blockquote>51 52<!-- begin en only -->53<p>54The first line of a dataset contains an integer <i>n</i> (3 &le; <i>n</i> &le; 100) 55representing the number of the circles.56Each of the following <i>n</i> lines contains three integers separated by a single space.57(<i>x</i><sub><i>i</i></sub>, <i>y</i><sub><i>i</i></sub>) 58and <i>r</i><sub><i>i</i></sub> represent 59the center position and the radius of the <i>i</i>-th circle <i>C</i><sub><i>i</i></sub>.60You can assume that 0 &le; <i>x</i><sub><i>i</i></sub> &le; 1000, 610 &le; <i>y</i><sub><i>i</i></sub> &le; 1000, and621 &le; <i>r</i><sub><i>i</i></sub> &le; 25.63</p>64<!-- end en only -->65 66<!-- begin en only -->67<p>68You can assume that <i>C</i><sub><i>i</i></sub>  and 69<i>C</i><sub><i>i</i>+1</sub>  (1 &le; <i>i</i> &le; <i>n</i>&minus;1) intersect at two separate points.70When <i>j</i> &ge; <i>i</i>+2, <i>C</i><sub><i>i</i></sub>  and <i>C</i><sub><i>j</i></sub>  are apart and either of them does not contain the other.71In addition, you can assume that any circle does not contain the center of any other circle.72</p>73<p>74The end of the input is indicated by a line containing a zero. 75</p>76<!-- end en only -->77 78<!-- begin en only -->79<p>80Figure E-1 corresponds to the first dataset of Sample Input below.81Figure E-2 shows the shortest paths for the subsequent datasets of Sample Input. 82 83</p>84<!-- end en only -->85 86<center>87<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_1183_2"><br><br>88<!-- begin en only -->89Figure E-2: Example chains and the corresponding shortest paths<br>90<!-- end en only -->91</center>92 93 94 95<h3>Output</h3>96 97<!-- begin en only -->98<p>99For each dataset, output a single line containing the length of the shortest chain-confined path between the centers of the first circle and the last circle.100The value should not have an error greater than 0.001.101No extra characters should appear in the output. 102</p>103<!-- end en only -->104 105 106 107<h3>Sample Input</h3>108 109<pre>11010111802 0 10112814 0 4113820 1 4114826 1 4115832 3 5116838 5 5117845 7 3118849 10 3119853 14 4120857 18 312131220 0 51238 0 51248 8 512531260 0 51277 3 612816 0 512991300 3 51318 0 813219 2 813323 14 613423 21 613523 28 613619 40 81378 42 81380 39 5139111400 0 51418 0 514218 8 101438 16 51440 16 51450 24 51463 32 514710 32 514817 28 814927 25 315030 18 51510152</pre>153 154 155<h3>Output for the Sample Input</h3>156 157<pre>15858.95343715911.41421416016.016161.87481216263.195179163</pre>164 165