prithivMLmods/Coder-Stat

1 2 3<H1><font color="#000000">Problem 10:</font> The Last Dungeon</H1>4 5<p>6勇者ポン太はいよいよ最終ダンジョンの目前までやってきた。ここは、悪の帝王ボロモスの砦の前に広がる闇の荒野であり、かなり強者のモンスターが、それぞれの縄張りを守っている。7</p>8 9<center>10<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_lastDangion1"><br>11<p>図１：荒野</p>12</center>13 14<p>15荒野は図１に示すように、南西を原点(0, 0)とした 4 &times; 4 の正方形の領域で表されている。この領域の中に、図の点で示されているように、モンスターが構えている。勇者ポン太はこの領域を西から東へ（WからEへ）横断しなければならない。つまり、x 座標が 0.0 であり y 座標が 0.0 以上 4.0 以下である点から出発し、x 座標が 4.0 であり y 座標が 0.0 以上 4.0 以下である点へ移動しなければならない。16</p>17 18<p>19モンスターは、敵が領域に進入すると、自分と敵との距離が他のどのモンスターと敵との距離よりも短い場合、敵に襲いかかってくる。20</p>21 22<p>23十分なアイテムもない今、ボロモスと戦う前になるべく戦いは避けたいのが本音のポン太だった。そこで、ポン太はあることに気づいた：自分との距離が最も短くなるモンスターが常に２匹以上存在する道を進めばモンスターに襲われることはない。24</p>25 26 27 28<p>29勇者ポン太が無傷でボロモスのもとに辿りつけるかは、あなたのコントロール操作にかかっている。30闇の荒野を抜ける最短距離を求めるプログラムを作成せよ。31</p>32 33<p>34参考として、図１における最短経路を図２に示す。35</p>36 37<center>38<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_lastDangion3"><br>39<p>図２：最短経路</p>40</center>41 42 43 44 45<H2>Input</H2>46<p>47入力として複数のデータセットが与えられる。各データセットは以下の形式で与えられる：<br><br>48<i>n</i> （モンスターの数：整数）<br>49<i>x</i><sub>1</sub> <i>y</i><sub>1</sub>　（１匹目のモンスターの位置：空白区切りの実数）<br>50<i>x</i><sub>2</sub> <i>y</i><sub>2</sub>　（２匹目のモンスターの位置：空白区切りの実数）<br>51.<br>52.<br>53<i>x</i><sub><i>n</i></sub> <i>y</i><sub><i>n</i></sub>　（<i>n</i> 匹目のモンスターの位置：空白区切りの実数）<br>54</p>55 56<p>57<i>n</i> は 1 以上 20 以下である。また、モンスターの位置を示す <i>x</i>, <i>y</i> 座標値は 0.0 以上 4.0 以下である。58</p>59 60<p>61<i>n</i> が 0 のとき入力の終わりを示す。62</p>63 64<H2>Output</H2>65<p>66各データセットについて、最短距離を1行に出力せよ。モンスターに襲われることなく荒野を横断することができない場合は "<span>impossible</span>" と出力せよ。67</p>68<p>69距離の出力は 0.00001 以下の誤差があっても良いものとする。70</p>71 72<H2>Sample Input</H2>73<pre>742751 1763 3774781.0 0.5791.0 2.5803.0 1.5813.0 3.5821832.0 2.084085</pre>86 87 88<H2>Output for the Sample Input</H2>89<pre>905.656854249492914.61803398875092impossible93</pre>94