The Last Dungeon

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem 10: The Last Dungeon

勇者ポン太はいよいよ最終ダンジョンの目前までやってきた。ここは、悪の帝王ボロモスの砦の前に広がる闇の荒野であり、かなり強者のモンスターが、それぞれの縄張りを守っている。


図1:荒野

荒野は図1に示すように、南西を原点(0, 0)とした 4 × 4 の正方形の領域で表されている。この領域の中に、図の点で示されているように、モンスターが構えている。勇者ポン太はこの領域を西から東へ(WからEへ)横断しなければならない。つまり、x 座標が 0.0 であり y 座標が 0.0 以上 4.0 以下である点から出発し、x 座標が 4.0 であり y 座標が 0.0 以上 4.0 以下である点へ移動しなければならない。

モンスターは、敵が領域に進入すると、自分と敵との距離が他のどのモンスターと敵との距離よりも短い場合、敵に襲いかかってくる。

十分なアイテムもない今、ボロモスと戦う前になるべく戦いは避けたいのが本音のポン太だった。そこで、ポン太はあることに気づいた:自分との距離が最も短くなるモンスターが常に2匹以上存在する道を進めばモンスターに襲われることはない。

勇者ポン太が無傷でボロモスのもとに辿りつけるかは、あなたのコントロール操作にかかっている。 闇の荒野を抜ける最短距離を求めるプログラムを作成せよ。

参考として、図1における最短経路を図2に示す。


図2:最短経路

Input

入力として複数のデータセットが与えられる。各データセットは以下の形式で与えられる:

n (モンスターの数:整数)
x1 y1 (1匹目のモンスターの位置:空白区切りの実数)
x2 y2 (2匹目のモンスターの位置:空白区切りの実数)
.
.
xn yn (n 匹目のモンスターの位置:空白区切りの実数)

n は 1 以上 20 以下である。また、モンスターの位置を示す x, y 座標値は 0.0 以上 4.0 以下である。

n が 0 のとき入力の終わりを示す。

Output

各データセットについて、最短距離を1行に出力せよ。モンスターに襲われることなく荒野を横断することができない場合は "impossible" と出力せよ。

距離の出力は 0.00001 以下の誤差があっても良いものとする。

Sample Input

2
1 1
3 3
4
1.0 0.5
1.0 2.5
3.0 1.5
3.0 3.5
1
2.0 2.0
0

Output for the Sample Input

5.656854249492
4.618033988750
impossible

Source: PC Koshien 2009 Warm-Up Contest , Aizu-Wakamatsu, Japan, 2009-08-22