国内予選問題

acm International Collegiate Programming Contest

問題文と入力データ,出力例

問題文 In/Out In/Out In/Out In/Out
A 1/ 1 2/ 2 3/ 3 4/ 4
B 1/ 1 2/ 2 3/ 3 4/ 4
C 1/ 1 2/ 2 3/ 3 4/ 4
D 1/ 1 2/ 2 3/ 3 4/ 4
E 1/ 1 2/ 2 3/ 3 4/ 4
F 1/ 1 2/ 2 3/ 3 4/ 4
G 1/ 1 2/ 2 3/ 3 4/ 4

入力データ・出力例をzip形式でまとめたものはこちらからダウンロードできます.

Links


Problem A

角角画伯,かく悩みき

角角画伯はキュービズムの大家として知らない人がいるとかいないとか…角角画伯の今年の主題は,正方形だそうです.今日は角角画伯のアトリエにお邪魔しています.

アトリエの中央には途方もなく大きなテーブルがあります.その傍らには同じ大きさに切り揃えられた正方形がたくさん用意されています.角角画伯は一 枚の正方形をテーブルの中央に置きました.それに続いて,他の正方形を順番に並べます.その様子を観察すると,画伯の几帳面な性格を反映しているのでしょ うか,どの正方形を置くときも,必ず別の正方形に隣接して置き,隣接した正方形の辺をぴたりと揃えているようです.

さあ最初の作品が完成したようです.画伯はごきげんのようです.どうです,この満足そうなお顔は.

あれ?おやおや,今度は画伯は頭を抱えてしまいました.どうしたことでしょう.ははあ.この作品を入れるのにぴったりの箱を注文したいのだけれどもその長さを測るのが大変だと嘆いておられます.さあ,みんなで画伯を手伝ってあげましょう.

画伯が完成させた作品のデータが与えられますので,その幅と高さを出力するプログラムを書いて下さい.正方形の一辺の長さは1とします.画伯が同じ位置に複数の正方形を積み重ねないことを仮定して構いません.

あれあれ,下の図を眺めながら「その十字架はもっと小さい箱に入るんじゃない」なんて言ってる人がいますね.角角画伯は悲しそうな顔で首を振りながら「斜めに入れるような人は自分の画風を理解していない」と言っていますよ.

Input

入力は複数のデータセットからなる.各データセットは,作品の制作手順を表したデータであり,その形式は次の通りである.

N
n1 d1
n2 d2
...
nN-1 dN-1

データセットの最初の行には作品を構成する正方形の数(= N)が与えられる.Nは1以上,200未満の整数である.

データセットの残りの(N-1)行は正方形の置き方を表している.“ni di”は,i (≤ N-1)番の正方形の置き方を指示している.ここで,正方形の番号は,テーブルの上に一番最初に置かれたものを0とし,その後,置いた順番に1, 2, …, (N-1)と番号づけられるものとする.なお0番の正方形に対する置き方の指示はない.

i番の正方形に対する置き方の指示 “ni di” は,i番の正方形をni番の正方形に対してdiで示される方角に隣接して置くことを指示する.ここで,diは0, 1, 2, 3のいずれかをとり,それぞれ左側(= 0),下側 (= 1),右側 (= 2),上側 (= 3)を表す.

例えば以下はSample Inputの四つのデータセットに対応した作品を図示したものである.図中の番号は,正方形の番号に相当する.

入力の終わりはひとつのゼロのみからなる行で表される.

Output

各データセットについて,作品の幅と高さを整数として,それぞれ1行に出力しなさい.幅と高さの間は1文字の空白で区切り,各出力行はこれら以外の文字を含んではならない.

Sample Input

1
5
0 0
0 1
0 2
0 3
12
0 0
1 0
2 0
3 1
4 1
5 1
6 2
7 2
8 2
9 3
10 3
10
0 2
1 2
2 2
3 2
2 1
5 1
6 1
7 1
8 1
0

Output for the Sample Input

1 1
3 3
4 4
5 6

Problem B

迷図と命ず

日本語では「迷路」と呼ぶことが多い maze だが,英語と発音を似せて「迷図」と呼ぶ人もいる.迷図を通り抜けられないようでは,国内予選を通過するのも難しいかも!

この問題の迷図は,四角を縦横に並べた長方形の領域である.この領域は出入口を除いて壁で囲まれている.迷図の入口は長方形の上辺の最も左側で,つまり最上段の最左の四角の上辺は開いている.出口は同様に下辺の最も右側にある.

迷図の中では縦または横に隣り合う四角に行くことができる.しかし隣とは壁で隔てられていることがあり,その場合直接には行き来できない.

あなたの仕事は,入口から出口までの最短経路の長さを求めることである.最短経路が複数あることもあれば,ひとつもないこともあるのに注意されたい.

Input

入力はそれぞれが迷図を表すひとつ以上のデータセットからなる.

データセットの最初の行には迷図の幅 w と高さ h を与えるふたつの整数値がこの順に入っている.

それに続く 2 × h − 1 行は,隣接する四角の間の壁の有無を示している.最初の行の先頭は空白で,その後には w −1 個の 1 または 0 が空白ひとつで区切られて並んでいる.これらは一番上の行の横に隣り合う四角の間の壁の有無を示すものである.1 は壁があることを,0 はないことを意味する. 次の行の先頭には空白はなく,w 個の 1または 0 が空白ひとつを区切りに続く.これらは最初と次の行の縦に隣り合う四角の間の壁の有無を表す.整数 1/0 は壁の有/無を示す.引き続く行は交互に横と縦に隣り合う四角の間の壁の有無を同様に表す.

入力の終わりは二つのゼロを含む行で表される.

データセット数は100以下である.長方形領域の高さも幅も2以上30以下である.

Output

各データセットについて,入口から出口までの最短経路長を表す整数ひとつを持つ行を出力せよ.ここでは経路の長さは通過する四角の数で表す.迷図を通り抜ける経路がない場合には,ゼロひとつを含む行を出力せよ.出力行にはこの数値以外の文字を含んではならない.

Sample Input

2 3
 1
0 1
 0
1 0
 1
9 4
 1 0 1 0 0 0 0 0
0 1 1 0 1 1 0 0 0
 1 0 1 1 0 0 0 0
0 0 0 0 0 0 0 1 1
 0 0 0 1 0 0 1 1
0 0 0 0 1 1 0 0 0
 0 0 0 0 0 0 1 0
12 5
 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0
 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0
 0 0 1 0 0 1 0 1 0 0 0
0 0 0 1 1 0 1 1 0 1 1 0
 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 0 0
0 0


Output for the Sample Input

4
0
20

Problem C

ポロック予想

n 番目の正三角形数は,最初の n 個の正整数の和と定義される.
n 番目の正四面体数は,最初の n 個の正三角形数の和と定義される.
簡単に示せるように,n 番目の正四面体数は n(n+1)(n+2) ⁄ 6 に等しい.
たとえば,5番目の正四面体数は 1+(1+2)+(1+2+3)+(1+2+3+4)+(1+2+3+4+5)
= 5×6×7 ⁄ 6
= 35 である.

最初の5個の正三角形数

1, 3, 6, 10, 15

Tr[1]Tr[2]Tr[3]Tr[4]Tr[5]

最初の5個の正四面体数

1, 4, 10, 20, 35

Tet[1]Tet[2]Tet[3]Tet[4]Tet[5]

1850年,職業数学者ではなく英国の法律家でありトーリー党(現在の保守党)の政治家でもあった初代准男爵フレデリック・ポロック卿が,すべての正整数は5個以内の正四面体数の和として表現できると予想した.
ただし,和の中で同じ正四面体数が複数回出現してよく,その場合,それぞれの出現を別々に数えるものとする.
この予想は一世紀半以上も未解決なままである.

あなたの任務は,
個別の整数に対してポロック予想が成り立つことを確認するプログラムを書くことである.
あなたのプログラムは,
入力された整数おのおのについて,
それを正四面体数の和として表すための正四面体数の個数の最小値を計算しなくてはならない.
なぜか,ついでに,
奇数の正四面体数だけ使える場合の同様の計算もしなくてはならない.

たとえば,
40は2個の正四面体数の和
4×5×6 ⁄ 6 + 4×5×6 ⁄ 6
として表すことができるが,
40自体は正四面体数ではない.
40は6個の奇数の正四面体数の和
5×6×7 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6 + 1×2×3 ⁄ 6
として表すことができるが,
より少ない個数の奇数の正四面体数の和として表すことはできない.
したがって,あなたのプログラムに40が与えられると,
2と6と答えなくてはならない.

Input

入力は行の並びで,
おのおのの行には 106 より小さい正整数がちょうど一つだけ含まれている.
入力の終わりは,一文字の 0 だけを含む行で示される.

Output

入力された正整数おのおのについて,
二つの整数を空白で区切った行を出力せよ.
一つめの整数は,
入力された整数を正四面体数の和として表すために必要な正四面体数の個数の最小値である.
二つめの整数は,
入力された整数を奇数の正四面体数の和として表すために必要な奇数の正四面体数の個数の最小値である.
出力に余分な文字が含まれてはならない.

Sample Input

40
14
5
165
120
103
106
139
0

Output for the Sample Input

2 6
2 14
2 5
1 1
1 18
5 35
4 4
3 37
(End of Problem C) ABCDEFG

Problem D

ぐらぐら

あなたの勤め先のピカソニアン・キュービズム国際センター(ICPC)の事務局では,若き芸術家のための美術館を新たに建設する.そのためセンターでは建物の設計コンペを開催することになった.

コンペに提出される図面は,下に示すように,かの有名なゲームの画面のようなものになる.

それというのも,センターが指定する工法が「ピース」と呼ばれる規格化されたユニットを積み重ねて建築するというものだからである.各ピースは4つの立方体のブロックをつなげて作られている.センターはさらに,応募される設計に次のような条件を課している.

  • ピースはブロック単位で位置を揃えてある.つまりピースとピースが接する場合,両者のブロックの面どうしはぴったり重なるような置き方しか許されない.
  • ピースは安定していなければいけない.ピースは積み重ねられるだけなので,崩れてしまわないように重心の位置を慎重に定めなければいけない.
  • ピースは樹状に積み重ねられ,それによって若き芸術家達の無限の可能性を象徴する.つまり,地面に接しているピースは唯1つだけで,それ以外の各ピースの下面が接しているピースは丁度1つだけに限られている.
  • 建物は平らな形に限られる.これは建設予定地が下図に示すようなお堀と高速道路にはさまれた狭い所で,お堀と高速道路の間にはブロック1個分の幅しかないためである.

建物の安定性を完全に調べるには,複雑な構造計算が必要なため何日もかかる.そこであなたは安定性の簡易診断を行うことを命じられた.簡易診断の方法は次のようである.

以下では各ブロックの重心はブロックの中心にあり,全てのブロックは同じ重さだと仮定する.また,ブロックの位置をブロックの左下のxy座標によって表す.単位はブロックの辺の長さである.

ピースを構成するブロックで下面が他のピースまたは地面に接しているもののうち,一番左のものの左端のx座標を xL,一番右のものの右端のx座標を xR とする.また,このピースによって直接または間接に支えられているすべてのピースとこのピース自身をあわせた全体の重心のx座標をMとする.このときxL < M < xR が成り立てばピースは安定であり,そうでなければ不安定である.建物を構成するピースが1つでも不安定であれば,その建物は不安定である.

上記の診断方法は,実際には崩れないような設計を不安定と判定する場合もあることに注意せよ.例えば,下図左の設計は不安定と判定される.

またこの診断方法は境界状態にある場合は不安定と判定することにも注意せよ.例えば,上図右の設計における上のピースの重心は,下のピースの右端の真上にあるが,これは不安定と判定される.

簡易診断方法によって各設計の安定性を診断するプログラムを書け.

Input

入力は複数のデータセットからなる.入力の終わりは空白1つで区切られた2個のゼロからなる行によって与えられる.各データセットは建物の正面図を表し,その形式は以下の通りである.

w h

p0(h-1)p1(h-1)...p(w-1)(h-1)

...

p01p11...p(w-1)1

p00p10...p(w-1)0

空白で区切られた整数wおよびhはそれぞれ配置の列数と行数を表す.ここで 1 ≤ w
10 かつ 1 ≤ h ≤ 60 と仮定してよい.続くh行はピースの配置を与える.pxyの文字は座標(x,y)のブロックの状態を表し,何もないことを表す「.」あるいはピースを構成するブロックを表す「1」から「9」までの数字のどれかである.(すでに述べたように,ブロックの位置はブロックの左下のxy座標によって表す.)

同じ数字を持つ2つのブロックが上下あるいは左右を接している場合,それらのブロックは同一のピースの部分である.(同じ数字を持つ異なる2つのピースが有り得ることに注意せよ.)座標(x,0)にあるブロックの下面は地面に接している.

各データセットは,ピースを樹状に積み重ねているものと仮定してよい.

Output

それぞれのデータセットについて,設計が上記の条件に従って安定な場合にはSTABLE, そうでない場合はUNSTABLEと全て大文字で書かれた行を出力せよ.出力にそれ以外の文字を含めてはならない.

Sample Input

4 5
..33
..33
2222
..1.
.111
5 7
....1
.1..1
.1..1
11..1
.2222
..111
...1.
3 6
.3.
233
23.
22.
.11
.11
4 3
2222
..11
..11
4 5
.3..
33..
322.
2211
.11.
3 3
222
2.1
111
3 4
11.
11.
.2.
222
3 4
.11
.11
.2.
222
2 7
11
.1
21
22
23
.3
33
2 3
1.
11
.1
0 0

Output for the Sample Input

STABLE
STABLE
STABLE
UNSTABLE
STABLE
STABLE
UNSTABLE
UNSTABLE
UNSTABLE
UNSTABLE

Problem E

最強の呪文

昔々,多くの「魔法の紋様」を発明した魔法使いがいた.
彼の発明した魔法の紋様が床に描かれた部屋では,
呪文を唱えることで,誰でも魔法が使えるようになるのだ!
ただし,使える呪文は紋様によってまちまちである.
あなたの仕事は,指定された魔法の紋様に対し,
それによって使用可能となる呪文のうち,最強のものを突き止めることだ.

呪文は,英小文字の文字列であり,
特に辞書順で早ければ早い呪文であるほど,強い呪文である.
ここで文字列 w が文字列 u より辞書順で早いとは,
w と u とで異なる最初の文字が a<b<...<z の順序で小さいか,
または w が u の接頭辞であることを言う.
例として,"abcd" は "abe" より早く(文字 c は e より小さいため),
また,"abe" は "abef" より早い(接頭辞になっているため).

魔法の紋様は,番号のついた 節点 と,それらを結ぶ矢印
からなる図形である.
矢印には ラベル と呼ばれる小文字の文字列がついている.
また,スターゴールド と呼ばれる,
二つの特別な節点がある.
魔法の紋様によって使えるようになる呪文とはすなわち,
その紋様のスターからゴールドへと矢印をたどって得られるラベルを順に結合して得られる文字列である.

次に,四つの節点と7本の矢印からなる例を図示する.


picture: sample dataset 1

0 がスター,2 がゴールドである.
この魔法の紋様によって,例えば

    
0 --"abra"--> 1 --"cada"--> 3 --"bra"--> 2

という経路から得られる呪文 "abracadabra" が使えるようになる.他には,

    
0 --"oil"--> 1 --"cada"--> 3 --"bra"--> 2 --"ket"--> 3 --"da"--> 3 --"da"--> 3 --"bra"--> 2

から得られる "oilcadabraketdadabra" などもある.
"abracadabra" と "oilcadabraketdadabra" では前者の方が辞書順で早いので,より強い呪文である.
実は,この魔法の紋様で使用可能となる呪文で "abracadabra" 以上に強いものは存在しない.
従ってこの場合,あなたが求めるべき答えは "abracadabra" となる.

もしも,最強の呪文が定められないときには,"NO" と答えて欲しい.
これには二つの場合がある.一つは,スターからゴールドへ到達できない場合である.
もう一つは,どんな呪文をとっても,
それよりさらに強い呪文が存在するような場合である.
たとえば次の図のような魔法の紋様では,
"b" よりも "ab" が強く,
"ab" よりも "aab" が強いといったように,
どの呪文をとってもさらに一つ a を増やすと,辞書順で早い,より強い呪文となる.


picture: sample dataset 2

Input

入力は最大で150個のデータセットからなる.
各データセットの形式は次のとおりである.

n a s g

x1 y1 lab1

x2 y2 lab2

...

xa ya laba

データセットの最初の行は4個の整数を含む.n は節点の数,a は矢印の数を表す.
sg はそれぞれスターとゴールドの番号を示す.
続く a 行はそれぞれ2個の整数と1個の文字列からなり,矢印の情報を表す.
xi yi labi という行は,
節点 xi から出て節点 yi を指す,
ラベルが labi の矢印を表している.
データセット中の値は次の条件を満たす:
2 ≤ n ≤ 40,
0 ≤ a ≤ 400,
0 ≤ s, g, xi , yi < n.
sg,
labi は長さ1以上6以下の,英小文字のみからなる文字列である.
矢印の両端が同一節点の場合 (xi = yi ) や,
節点の対を複数の矢印が結ぶ場合
(異なる i, j に対し
xi = xj かつ yi = yj )
もあり得ることに注意して欲しい.

入力の終わりは4個のゼロからなる行によって与えられる.

Output

各データセットについて,最も強い呪文が存在すれば,それぞれ1行に出力しなさい.
存在しない場合は NO を1行に出力しなさい.
各出力行はこれ以外の文字を含んではならない.

Sample Input

4 7 0 2
0 1 abra
0 1 oil
2 0 ket
1 3 cada
3 3 da
3 2 bra
2 3 ket
2 2 0 1
0 0 a
0 1 b
5 6 3 0
3 1 op
3 2 op
3 4 opq
1 0 st
2 0 qr
4 0 r
2 1 0 1
1 1 loooop
0 0 0 0

Output for the Sample Input

abracadabra
NO
opqr
NO

Problem F

古い記憶

西暦4272年,プログラミング文学の巨匠,アイザック・コーネル・パンサーキャロル博士は
三度の世界コンピューターウイルス大戦を奇跡的に生き残り,
今年で丁度90歳になったところでノーベル文学賞を受賞した.
メディアは彼の一生を細大漏らさず報道したが,一つだけ報道できなかったことがあった――それは彼がまだ小学生の頃に書いた作文だった.
彼は作文を保管しておいたので,それを報道陣に見せることを快諾したのだが,
最大の問題は,第三次世界コンピューターウイルス大戦の際に保管していた媒体が
コンピューターウイルスに何回か感染していたので,文章が改ざんされているかもしれない点だ.

更に調査を進めたところ,保管していた作文はやはり改ざんされていることが分かった.なぜ分かったのか?
80年以上前に,彼のクラスメートは感染する前に元の作文を脳に転送していたのだ.
半導体脳の発明により,人は脳に転送した文章を何世紀にもわたって完全に保持することができる.
容量が限られているため,文章全体を覚えている人はいなかったが,
我々はなんとかして文章の一部をクラスメートの一人の脳から引き出した.悲しいことに,それは手元に保管していた作文と完全には一致していなかった.
これはウイルス感染が無ければありえないことだ.

現在,そのコンピューターウイルスについて分かっていることは,ウイルスが作文に感染するたびに以下のうちどれか一つを行うことである.

  1. ウイルスはランダムな文字を文章中のランダムな位置に挿入する.(例:"ABCD" → "ABCZD")
  2. ウイルスは文章中の文字を1文字ランダムに選び,その文字を別の文字に変換する.(例:"ABCD" → "ABXD")
  3. ウイルスは文章中の文字を1文字ランダムに選び,その文字を文章中から取り除く.(例:"ABCD" → "ACD")

また,侵入ログの量から推定することでウイルス感染が起こりえた回数の最大値も貴方は知っている.
幸運なことに,彼のクラスメートのほとんどは彼の作文の少なくとも一部(以降ピースと呼ぶ)を覚えていてくれたようなのだ.
全ての証拠を総合すれば,元の作文を復元できるかもしれない.
貴方はジャーナリスト兼コンピュータ科学者として,元の作文に書かれていた文章としてどのようなものがあり得るのか,与えられたピースや改ざんされてしまった手元の文章を元に計算するコンピュータープログラムを書きたい.

Input

入力は複数のデータセットからなる.データセット数は100以下である.
データセットは以下の形式をしている.

d n

改ざん文章

ピース1

ピース2

...

ピースn

データセットの1行目は二つの正の整数 d (d ≤ 2) と n (n ≤ 30) からなり,
dは作文にウイルスが感染した回数の最大値を,nはピースの数を表している.

データセットの2行目は,手元にある改ざんされた文章である.以降これを「改ざん文章」と呼ぶ.
改ざん文章の長さは40文字以下である.

データセット中の残りの行はピースと呼ばれ,彼のクラスメートが覚えていた元の作文の一部である.
各々のピースは20文字以下で,最低13文字ある.ピースは全て同じ長さである.
改ざん文章やピースに現れる文字は,英語アルファベット大文字(`A'から`Z')とピリオド(`.')である.
彼が用いていた言語は分かち書きをしないので,ピースや改ざん文章中に空白文字は現れない.

二つのゼロのみを含む行が入力の終わりを表す.

クラスメートは充分にたくさんいたので,元の作文中にあるどの文字も必ず最低一つのピースでカバーされていると仮定してよい.
一つのピースが元の作文を2回以上カバーすることがある.元の作文には繰り返しがあるかもしれない.
また,彼のクラスメートは勘違いをして関係ないピースを提出したかもしれないので,幾つかのピースは元の作文中に現れないかもしれないことに注意せよ.

Output

各データセットに対して何を出力すれば良いかを以下に説明する.
与えられたピースや改ざん文書と合う元の作文が c 種類有り得るとする.
最初に c を含む1行を出力せよ.
もしcが5以下の場合には,さらに辞書順で1行に一つずつそれらの可能性を表示せよ.
辞書順では '.' が他のどの文字よりも早いことに注意せよ.
cは0でないことを仮定して良い.
上記で指示されていないいかなる文字も出力してはならない.

Sample Input

1 4
AABBCCDDEEFFGGHHIJJKKLLMMNNOOPP
AABBCCDDEEFFGG
CCDDEEFFGGHHII
FFGGHHIIJJKKLL
JJKKLLMMNNOOPP
2 3
ABRACADABRA.ABBRACADABRA.
ABRACADABRA.A
.ABRACADABRA.
BRA.ABRACADAB
2 2
AAAAAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
2 3
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXAXXXXXX
XXXXXXBXXXXXX
XXXXXXXXXXXXX
0 0

Output for the Sample Input

1
AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPP
5
.ABRACADABRA.ABRACADABRA.
ABRACADABRA.A.ABRACADABRA.
ABRACADABRA.AABRACADABRA.A
ABRACADABRA.ABRACADABRA.
ABRACADABRA.ABRACADABRA.A
5
AAAAAAAAAAAAAA
AAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAA
257

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