prithivMLmods/Coder-Stat

1 2<script type="text/x-mathjax-config">3  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});4</script>5<script type='text/javascript' src='http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML'></script>6</script>7 8<h2>Problem H:9Cornering at Poles10</h2>11 12<p>13  You are invited to a robot contest. In the contest, you are given a disc-shaped robot that is placed on a flat field. A set of poles are standing on the ground. The robot can move in all directions, but must avoid the poles. However, the robot can make turns around the poles touching them.14</p>15 16<p>17  Your mission is to find the shortest path of the robot to reach the given goal position. The length of the path is defined by the moving distance of the center of the robot. Figure H.1 shows the shortest path for a sample layout. In this figure, a red line connecting a pole pair means that the distance between the poles is shorter than the diameter of the robot and the robot cannot go through between them.18</p>19 20<center>21<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ICPCAsia2014_H1" width="600"><br>22<p>Figure H.1. The shortest path for a sample layout</p>23</center>24 25<h3>Input</h3>26 27<p>28  The input consists of a single test case.<br>29  <br>30$N$ $G_x$ $G_y$<br>31$x_1$ $y_1$<br>32.<br>33.<br>34.<br>35$x_N$ $y_N$<br>36<br>37 38The first line contains three integers. $N$ represents the number of the poles ($1 \leq N \leq 8$). $(G_x, G_y)$ represents the goal position. The robot starts with its center at $(0, 0)$, and the robot accomplishes its task when the center of the robot reaches the position $(G_x, G_y)$. You can assume that the starting and goal positions are not the same.39</p>40 41<p>42  Each of the following $N$ lines contains two integers. $(x_i, y_i)$ represents the standing position of the $i$-th pole. Each input coordinate of $(G_x, G_y)$ and $(x_i, y_i)$ is between $−1000$ and $1000$, inclusive. The radius of the robot is $100$, and you can ignore the thickness of the poles. No pole is standing within a $100.01$ radius from the starting or goal positions. For the distance $d_{i,j}$ between the $i$-th and $j$-th poles $(i \ne j)$, you can assume $1 \leq d_{i,j} < 199.99$ or $200.01 < d_{i,j}$.43																																																															 </p>44 45<p>46Figure H.1 shows the shortest path for Sample Input 1 below, and Figure H.2 shows the shortest paths for the remaining Sample Inputs.47</p>48 49<center>50<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ICPCAsia2014_H2" width="640"><br>51<p>Figure H.2. The shortest paths for the sample layouts</p>52</center>53 54 55<h3>Output</h3>56 57<p>58Output the length of the shortest path to reach the goal. If the robot cannot reach the goal, output 0.0. The output should not contain an error greater than 0.0001.59</p>60 61 62 63<h3>Sample Input 1</h3>64 65<pre>8 900 06640 1006770 -8068350 3069680 -2070230 23071300 40072530 1307375 -275</pre>74 75<h3>Sample Output 1</h3>76 77<pre>1210.99416</pre>78 79<h3>Sample Input 2</h3>80 81<pre>1 0 20082120 0</pre>83 84<h3>Sample Output 2</h3>85 86<pre>200.0</pre>87 88<h3>Sample Input 3</h3>89 90<pre>3 110 110910 11092110 093200 10</pre>94 95<h3>Sample Output 3</h3>96 97<pre>476.95048</pre>98 99<h3>Sample Input 4</h3>100 101<pre>4 0 20010290 90103-90 90104-90 -9010590 -90</pre>106 107<h3>Sample Output 4</h3>108 109<pre>0.0</pre>110 111<h3>Sample Input 5</h3>112 113<pre>2 0 -21011420 -105115-5 -105</pre>116 117<h3>Sample Output 5</h3>118 119<pre>325.81116</pre>120 121<h3>Sample Input 6</h3>122 123<pre>8 680 -5012480 8012580 -100126480 -120127-80 -110128240 -90129-80 100130-270 100131-420 -20</pre>132 133<h3>Sample Output 6</h3>134 135<pre>1223.53071</pre>136 137 138 139 140