Laser Beam Reflections

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem G: レーザー光の反射

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

図 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

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

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2010-07-02
http://icpc2010.honiden.nii.ac.jp/