Milky Way

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

Milky Way

天の川

English text is not available in this practice contest.

天の川交通公社は星間旅行ツアーの企画・運営を行う旅行会社である。 天の川交通公社では「天の川横断織姫彦星体験ツアー」という企画を計画中である。 このツアーは琴座のベガを出発し、 星々を巡って鷲座のアルタイルに向かうというものである。 あなたは天の川交通公社に社員であり、 ツアーの経路の選択を任されている。

簡単のため天の川は2次元座標上にあるものとし、 星は五芒星で表現されるものとする。 ツアーに使用する宇宙船には特殊なエンジンが搭載されており、 五芒星の線分上はエネルギー無しで移動することができる。 一方、五芒星の間を移動する際には、その距離に比例したエネルギーが必要となる。

近年、天の川交通公社の売上は低迷しており、 宇宙船のエネルギー代を始めとした各種必要経費の節約を迫られている。 あなたの仕事は、ベガからアルタイルに移動する際、 星間移動距離の総和が最小になるような経路を求め、 その総和を出力するプログラムを書くことである。

ある五芒星からその内部に含まれる別の五芒星に移動する場合、 五芒星同士が接していない場合は星間の移動として扱われることに注意せよ。

図D-1は3つ目のSample Inputを図示したものである。 図中、赤色の線分は星間移動距離の総和が最小になるような経路の、 星間移動の部分を表している。

図 D-1: 星間の移動

Input

入力は1つ以上のデータセットからなる。1つのデータセットは次の形式をしている。

N M L
x1 y1 a1 r1
x2 y2 a2 r2
...
xN yN aN rN

各テストケースの初めの1行は整数N、M、Lからなり、 Nは星の数(1 ≤ N ≤ 100)、 Mはベガの番号(1 ≤ M ≤ N)、 Lはアルタイルの番号(1 ≤ L ≤ N)を表す。 続くN行には各星の情報が与えられる。 各行はxi、yi、ai、riの4つの整数からなり、 xiはi番目の星の中心のx座標(0 ≤ xi ≤ 1,000)、 yiはi番目の星の中心のy座標(0 ≤ yi ≤ 1,000)、 aiはi番目の星の中心座標と星の先端を結んだ直線がy軸となす角度(0 ≤ ai < 72)、 riはi番目の星の中心座標から星の先端までの長さ(1 ≤ ri ≤ 1,000)である。 入力の終わりは3つのゼロを含む行で表される。

図 D-2の左の星はx=5, y=10, a=0, r=5の星を表しており、右の星はx=15, y=10, a=30, r=5の星を表している。

図 D-2: 星の例

Output

各入力ごとに、ベガからアルタイルに移動する際に必要な星間移動距離の総和の最小値を1行に出力せよ。 出力には、0.000001を超える誤差があってはならない。

Sample Input

1 1 1
5 5 0 5
2 1 2
5 5 0 5
15 5 0 5
3 2 3
15 15 0 5
5 5 10 5
25 25 20 5
0 0 0

Output for Sample Input

0.00000000000000000000
0.48943483704846357796
9.79033725601359705593

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