AT_abc374_d [ABC374D] Laser Marking

[problemUrl]: https://atcoder.jp/contests/abc374/tasks/abc374_d $ xy $ 平面に対し、レーザを照射しながら線分を印字する印字機があります。 - 印字開始時、レーザ照射位置は座標 $ (0,\ 0) $ にある。 - 線分を印字する際は、以下の流れに従う。 - まず、レーザ照射位置を線分の端点のうちどちらか $ 1 $ つに移動させる。 - どちらの端点から描画を始めてもよい。 - その後、レーザ照射位置のある端点からもう一方の端点まで、レーザを照射しながらレーザ照射位置を一直線に移動させる。 - 線分の途中で印字を中止することは許されない。 - レーザを照射していない時、レーザ照射位置は $ 1 $ 秒あたり速度 $ S $ で任意の方向に移動できる。 - レーザを照射している時、レーザ照射位置は $ 1 $ 秒あたり速度 $ T $ で印字中の線分に沿って移動できる。 - レーザ照射位置の移動にかかる時間以外の所要時間は無視できる。 高橋君はこの印字機で $ N $ 本の線分を印字したいです。 そのうち $ i $ 本目の線分は、座標 $ (A_i,\ B_i) $ と座標 $ (C_i,\ D_i) $ を結びます。 なお、複数の線分が重なっていることがありますが、全ての線分についてその都度重なっている部分を印字する必要があります。 うまく印字機を操作したとき、全ての線分を印字完了するまでにかかる最小の時間は何秒ですか？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $ $ T $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $ \vdots $ $ A_N $ $ B_N $ $ C_N $ $ D_N $

答えを出力せよ。 なお、真の値との絶対誤差または相対誤差が $ 10^{-6} $ 以下であれば正解として扱われる。

### 制約 - 入力は全て整数 - $ 1\ \le\ N\ \le\ 6 $ - $ 1\ \le\ T\ \le\ S\ \le\ 1000 $ - $ -1000\ \le\ A_i,B_i,C_i,D_i\ \le\ 1000 $ - $ (A_i,B_i)\ \neq\ (C_i,D_i) $ ( $ 1\ \le\ i\ \le\ N $ ) ### Sample Explanation 1 \- レーザを照射しながらレーザ照射位置を $ (0,0) $ から $ (0,2) $ まで移動させ、 $ 2 $ 本目の線分を描画する。 - この描画に要する時間は $ 2 $ 秒である。 - レーザを照射せずレーザ照射位置を $ (0,2) $ から $ (1,3) $ まで移動させる。 - この移動に要する時間は $ \sqrt{2}/2 $ 秒である。 - レーザを照射しながらレーザ照射位置を $ (1,3) $ から $ (2,1) $ まで移動させ、 $ 1 $ 本目の線分を描画する。 - この描画に要する時間は $ \sqrt{5} $ 秒である。 - レーザを照射せずレーザ照射位置を $ (2,1) $ から $ (2,0) $ まで移動させる。 - この移動に要する時間は $ 1/2 $ 秒である。 - レーザを照射しながらレーザ照射位置を $ (2,0) $ から $ (3,0) $ まで移動させ、 $ 3 $ 本目の線分を描画する。 - この描画に要する時間は $ 1 $ 秒である。 - 全体の所要時間は $ 2\ +\ (\sqrt{2}/2)\ +\ \sqrt{5}\ +\ (1/2)\ +\ 1\approx\ 6.443175 $ 秒です。 ### Sample Explanation 3 複数の線分が重なっていますが、全ての線分についてその都度重なっている部分を印字する必要があります。