Kuru Kuru Door

時間制限 : 8 sec, メモリ制限 : 262144 KB

Kuru Kuru Door

くるくるドア

ACM (Automatic Cleaning Machine) 社が2011年に開発した全自動円形掃除機 ICPC (Intelligent Circular Perfect Cleaner) は, 日中に自動で動き出し,自分が通り過ぎた場所のゴミを掃除する機能を備えている. 加えて,この ICPC は,バッテリー残量が低下した場合に自動的に電源の位置まで戻る機能も備えている.

この度,JAG (Japan Alumni Group) と名乗る謎の組織から, ACM 社に対し大量の ICPC の発注があった. しかし,その発注には条件が付いていた. それは,彼らが本拠地としているビルの内部にある「くるくるドア」に ICPC を対応させることである. くるくるドアは,以下に述べるように平面上の物体としてモデル化されている.

くるくるドアは,原点で接続された長さ R の 2n (≥ 4) 枚のドアの組として表される. これらのドアは,角度 π/n おきに並んでいる. くるくるドアは手動であり,ドアのどこに触れても触れた方向( ICPC との重なりが解消される方向)へ原点中心に一斉に回転させることができるが, 平行移動させることはできない. 初期状態では,ドアのちょうど2枚が y 軸に平行である.

また,原点を中心とする半径 R の円のうち,y 座標の絶対値が Rsin(π/(2n)) 以上である部分および, y 軸上で y 座標の絶対値が R 以上の部分は壁になっている. これらの壁は押すことができない.

平面上で ICPC は半径 r の円として表される. ICPC の電源は点 T = (xt, yt) にあり, ICPC はその中心座標が電源の位置に重なっている時バッテリーを充電することができる. はじめに ICPC の中心座標が点 S = (xs, ys) となる位置にあるとき, 電源の位置まで ICPC が最短経路を通って戻れるようにすることが, JAG から出された ICPC 発注の条件である. なお, ICPC がくるくるドアに対して正確な挙動を行うことを確かめるために, ICPC の初期位置と電源の位置は,くるくるドアを挟んで反対側となるように与えられる. ACM 社は,凄腕プログラマーのあなたに,くるくるドアの寸法, ICPC の中心座標 S と半径,電源の位置 T が与えられたとき,ICPCが電源の位置へ到達できるかを判定し,到達可能な場合は ICPC の中心座標が移動する最短経路の長さを求めるプログラムの作成を依頼した.

Input

入力は,複数のデータセットから構成され,1つの入力に含まれるデータセットの数は60個以下である. 各データセットの形式は次の通りである.

n
r R
xs ys
xt yt

n はくるくるドアを構成するドアの枚数の半分を表す整数であり,2 ≤ n ≤ 10 と仮定して良い. rR はそれぞれ ICPC の半径,くるくるドアの一枚あたりの長さを表す整数であり,1以上10以下と仮定して良い.

(xs, ys) は ICPC の初期位置の中心座標,(xt, yt) は電源の位置を表す. xsysxtyt はそれぞれ整数であり,-1,000 ≤ xs ≤ - r - 1, -1,000 ≤ ys ≤ 1,000, r + 1 ≤ xt ≤ 1,000, -1,000 ≤ yt ≤ 1,000 を満たすと仮定して良い. 加えて,点 (xs, ys), (xt, yt) はそれぞれ原点から距離 R + r + 10-6 以上離れていると仮定して良い. すなわち, ICPC と電源は初期状態でいずれもくるくるドアの外側にあり,互いにくるくるドアを挟んで反対側に位置している.

また,r および R が 10-6 だけ変化しても, ICPC の電源位置への到達可能性は変わらないと仮定して良い.

入力の終わりは1つのゼロだけからなる行で示される.

下図は後に示す Sample Input 中の最初のデータセットにおける, ICPC の初期位置 S ,電源位置 T ,くるくるドアおよび壁の配置を表している.

Output

各データセットについて, ICPC が電源の位置に到達できる場合は,電源の位置までの移動距離の最小値を1行に出力せよ. この場合,出力の絶対誤差は 10-6 以内でなくてはならない. 到達できない場合は,-1 を1行に出力せよ.

Sample Input

3
1 4
-5 5
5 -5
10
1 10
-10 5
5 -10
5
3 5
-20 0
20 0
8
1 9
-14 58
6 24
2
2 8
-57 -113
42 -31
4
1 4
-4 -5
4 5
0

Output for Sample Input

17.5032106371
41.3850388846
-1
102.0656847372
178.1399151364
19.5548716821

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2015, 2015-06-14
http://acm-icpc.aitea.net/