prithivMLmods/Coder-Stat

1 2<!-- begin en only -->3<h1><font color="#000000">Problem G:</font>  Laser Beam Reflections</h1>4<!-- end en only -->5 6 7 8<!-- begin en only -->9<p>10A laser beam generator, a target object and some mirrors are 11placed on a plane.12The mirrors stand upright on the plane,13and both sides of the mirrors are flat and can reflect beams.14To point the beam at the target,15you may set the beam to several directions because of different reflections.16Your job is to find the shortest beam path17from the generator to the target and answer the length of the path.18</p>19<!-- end en only -->20 21<!-- begin en only -->22<p>23Figure G-1 shows examples of possible beam paths,24where the bold line represents the shortest one.25</p>26<!-- end en only -->27 28<center>29<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_D2010_G-0" align="center"><br><br>30<!-- begin en only -->31Figure G-1: Examples of possible paths32<!-- end en only -->33</center>34 35 36<h3>Input</h3>37 38 39 40<!-- begin en only -->41<p>42The input consists of a number of datasets. The end of the input is indicated by a line containing a zero. 43</p>44<!-- end en only -->45 46 47<!-- begin en only -->48<p>49Each dataset is formatted as follows. 50Each value in the dataset except <i>n</i> is an integer no less than 0 and no more than 100.51</p>52<!-- end en only -->53 54<p></p>55 56<blockquote>57<i>n</i><br>58<i>PX</i><sub>1</sub> <i>PY</i><sub>1</sub> <i>QX</i><sub>1</sub> <i>QY</i><sub>1</sub><br>59...<br>60<i>PX<sub><i>n</i></sub></i> <i>PY<sub><i>n</i></sub></i> <i>QX<sub><i>n</i></sub></i> <i>QY<sub><i>n</i></sub></i><br>61<i>TX</i> <i>TY</i><br>62<i>LX</i> <i>LY</i><br>63</blockquote>64 65<p></p>66 67<!-- begin en only -->68<p>69The first line of a dataset contains an integer <i>n</i> (1 &le; <i>n</i> &le; 5),70representing the number of mirrors.71The following <i>n</i> lines list the arrangement of mirrors on the plane.72The coordinates73(<i>PX<sub>i</sub></i>, <i>PY<sub>i</sub></i>) and 74(<i>QX<sub>i</sub></i>, <i>QY<sub>i</sub></i>) represent75the positions of both ends of the mirror.76Mirrors are apart from each other.77The last two lines represent the target position (<i>TX</i>, <i>TY</i>)78and the position of the beam generator (<i>LX</i>, <i>LY</i>).79The positions of the target and the generator are apart from each other,80and these positions are also apart from mirrors.81</p>82<!-- end en only -->83 84 85<!-- begin en only -->86<p>87The sizes of the target object and the beam generator are small enough to be ignored.88You can also ignore the thicknesses of mirrors.89</p>90<!-- end en only -->91 92<!-- begin en only -->93<p>94In addition, you can assume the following conditions on the given datasets.95<ul>96<li>There is at least one possible path from the beam generator to the target.97</li>98<li>The number of reflections along the shortest path is less than 6.99</li>100<li>101The shortest path does not cross or touch a plane containing a mirror102surface at any points within 0.001 unit distance from either end of the mirror.103</li>104<li>105Even if the beam could arbitrarily select reflection or passage 106when it reaches each plane containing a mirror surface107at a point within 0.001 unit distance from one of the mirror ends,108any paths from the generator to the target would not be 109shorter than the shortest path.110</li>111<li>112When the beam is shot from the generator in an arbitrary direction and 113it reflects on a mirror or passes the mirror within 0.001 unit distance from the mirror,114the angle <i>&theta;</i> formed by the beam and the mirror 115satisfies sin(<i>&theta;</i>) > 0.1, 116until the beam reaches the 6th reflection point (exclusive).117</li>118</ul>119</p>120<!-- end en only -->121 122 <!-- begin en only -->123<p>124Figure G-1 corresponds to the first dataset of the Sample Input below.125Figure G-2 shows the shortest paths for the subsequent datasets of the Sample Input.126</p>127<!-- end en only -->128 129<center>130<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_D2010_G-2" align="center"><br><br>131<!-- begin en only -->132Figure G-2: Examples of the shortest paths 133<!-- end en only -->134</center>135 136 137<h3>Output</h3>138 139<!-- begin en only -->140<p>141For each dataset, output a single line containing the length of the shortest path from142the beam generator to the target.143The value should not have an error greater than 0.001.144No extra characters should appear in the output.145</p>146<!-- end en only -->147 148 149<h3>Sample Input</h3>150 151 152<pre>153215430 10 30 7515560 30 60 9515690 01570 100158115920 81 90 9016010 9016190 10162216310 0 10 5816420 20 20 581650 7016630 016741688 0 8 6016916 16 16 4817016 10 28 3017116 52 28 3417224 017324 6417451758 0 8 6017616 16 16 4817716 10 28 3017816 52 28 34179100 0 100 5018024 018124 641820183</pre>184 185 186<h3>Output for the Sample Input</h3>187 188<pre>189180.27756377319946190113.1370849898476119198.9949493661166619290.5096679918780919390.50966799187809194</pre>195 196 197 198 199 200 201 202 203 204 205 206