Problem G: レーザー光の反射

レーザー光発生装置が，目標物やいくつかの鏡とともに，水平面上に設置されている． 鏡は平面上で直立しており，その両面ともに平面であり，レーザー光を反射することができる． 異なる反射を使うことにより，レーザー光を目標物に向ける方向は複数ありうる． あなたの仕事は，装置から目標物に至るレーザー光の最短経路を求め，その長さを答えることである．

図 G-1 は，複数の経路の例を示したものであり， 太線は最短経路を表している．

図 G-1: 可能な経路の例

Input

入力は複数のデータセットからなり，入力の終わりは，ゼロを一つだけ含む行で表される．

各データセットの形式は次のとおりである． データセット中の n 以外の値は，すべて 0 以上 100 以下の整数である．

n
PX₁ PY₁ QX₁ QY₁
...
PX_n PY_n QX_n QY_n
TX TY
LX LY

データセットの最初の行は，鏡の枚数を表す整数 n (1 ≤ n ≤ 5) である． 引き続く n 行は，それぞれの鏡の水平面上の位置を示し， 座標 (PX_i, PY_i) と (QX_i, QY_i) が， 鏡の両端の位置を表している． 鏡同士は，互いに離れて位置している． 最後の 2 行は，目標物の位置 (TX, TY) と， レーザー光発生装置の位置 (LX, LY) を示している． 目標物とレーザー光発生装置の位置は互いに異なり， また，両者とも鏡から離れている．

レーザー光発生装置及び目標物の大きさは 0 と仮定してよいほど小さい． 鏡の厚みについても無視してよい．

また，与えられたデータセットについて，以下のような仮定をしてよい．

• レーザー光発生装置から目標物に至る経路は，少なくとも一つ存在する．
• 最短経路における反射回数は 6 回未満である．
• 最短経路は，どちらかの端から 0.001 単位距離以内の点で 鏡面を含む平面と交差もしくは接することはない．
• 仮に，ビーム光が鏡面を含む平面にどちらかの端から 0.001 単位距離以内の点で到達した際に， 反射するか通過するかを任意に選択できたとしても， レーザー光発生装置から目標物への経路が，最短経路より短くなることはない．
• 装置から任意の方向に照射されたレーザー光は， 6 回目の反射点に到達する (6 回目の反射は含まない)までは， 鏡で反射する際， もしくは鏡から 0.001 単位距離の範囲を通過する際に， 鏡と光の経路がなす角 θ について，sin(θ) > 0.1 を満たす．

図 G-1 は，後に示す Sample Input 中の最初のデータセットに対応する． 図 G-2 は，Sample Input の引き続くデータセットに対する最短経路を示したものである．

図 G-2: 最短経路の例

Output

各データセットに対して，レーザー光発生装置から目標物に至るレーザー光の最短経路 の長さを，一行に出力せよ． 答えには 0.001 を越える誤差があってはいけない． それ以外の余計な文字を出力してはならない．

Sample Input

2
30 10 30 75
60 30 60 95
90 0
0 100
1
20 81 90 90
10 90
90 10
2
10 0 10 58
20 20 20 58
0 70
30 0
4
8 0 8 60
16 16 16 48
16 10 28 30
16 52 28 34
24 0
24 64
5
8 0 8 60
16 16 16 48
16 10 28 30
16 52 28 34
100 0 100 50
24 0
24 64
0

Output for the Sample Input

180.27756377319946
113.13708498984761
98.99494936611666
90.50966799187809
90.50966799187809

---