007 - レーザー光の反射

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

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

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

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

各データセットの形式は次のとおりである．
データセット中の 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: 最短経路の例

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

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

180.27756377319946
113.13708498984761
98.99494936611666
90.50966799187809
90.50966799187809