007 - レーザー光の反射

時間制限 8 秒 / メモリ制限 64 MB / 得点 20 / x 0 /


誤差
1e-3
TLE
8sec
MLE
64MB
得点
20

問題

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

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




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

Input

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

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

n

PX1 PY1 QX1 QY1

...

PXn PYn QXn QYn

TX TY

LX LY

データセットの最初の行は,鏡の枚数を表す整数 n (1 ≤ n ≤ 5) である.
引き続く n 行は,それぞれの鏡の水平面上の位置を示し,
座標 (PXi, PYi) と
(QXi, QYi) が,
鏡の両端の位置を表している.
鏡同士は,互いに離れて位置している.
最後の 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/Output

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