D - Laser Marking 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 350 点

問題文

xy 平面に対し、レーザを照射しながら線分を印字する印字機があります。

  • 印字開始時、レーザ照射位置は座標 (0, 0) にある。

  • 線分を印字する際は、以下の流れに従う。

    • まず、レーザ照射位置を線分の端点のうちどちらか 1 つに移動させる。
      • どちらの端点から描画を始めてもよい。
    • その後、レーザ照射位置のある端点からもう一方の端点まで、レーザを照射しながらレーザ照射位置を一直線に移動させる。
      • 線分の途中で印字を中止することは許されない。

  • レーザを照射していない時、レーザ照射位置は 1 秒あたり速度 S で任意の方向に移動できる。

  • レーザを照射している時、レーザ照射位置は 1 秒あたり速度 T で印字中の線分に沿って移動できる。
  • レーザ照射位置の移動にかかる時間以外の所要時間は無視できる。

高橋君はこの印字機で N 本の線分を印字したいです。
そのうち i 本目の線分は、座標 (A_i, B_i) と座標 (C_i, D_i) を結びます。
なお、複数の線分が重なっていることがありますが、全ての線分についてその都度重なっている部分を印字する必要があります。

うまく印字機を操作したとき、全ての線分を印字完了するまでにかかる最小の時間は何秒ですか？

制約

  • 入力は全て整数
  • 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 )

入力

入力は以下の形式で標準入力から与えられる。

N S T
A_1 B_1 C_1 D_1
\vdots
A_N B_N C_N D_N

出力

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

入力例 1

3 2 1
1 3 2 1
0 2 0 0
3 0 2 0

出力例 1

6.44317475868633722080
  • レーザを照射しながらレーザ照射位置を (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 秒です。

入力例 2

2 1 1
0 0 10 10
0 2 2 0

出力例 2

20.97056274847714058517

入力例 3

6 3 2
-1000 -1000 1000 1000
1000 -1000 -1000 1000
-1000 -1000 1000 1000
1000 -1000 -1000 1000
1000 1000 -1000 -1000
-1000 1000 1000 -1000

出力例 3

9623.35256169626864153344

複数の線分が重なっていますが、全ての線分についてその都度重なっている部分を印字する必要があります。

入力例 4

6 10 8
1000 1000 -1000 -1000
1000 -1000 -1000 -1000
-1000 1000 1000 1000
-1000 1000 -1000 -1000
1000 1000 1000 -1000
1000 -1000 -1000 1000

出力例 4

2048.52813742385702910909

Score : 350 points

Problem Statement

There is a printing machine that prints line segments on the xy-plane by emitting a laser.

  • At the start of printing, the laser position is at coordinate (0, 0).

  • When printing a line segment, the procedure below is followed.

    • First, move the laser position to one of the endpoints of the line segment.
      • One may start drawing from either endpoint.
    • Then, move the laser position in a straight line from the current endpoint to the other endpoint while emitting the laser.
      • It is not allowed to stop printing in the middle of a line segment.

  • When not emitting the laser, the laser position can move in any direction at a speed of S units per second.

  • When emitting the laser, the laser position can move along the line segment being printed at a speed of T units per second.
  • The time required for operations other than moving the laser position can be ignored.

Takahashi wants to print N line segments using this printing machine.
The i-th line segment connects coordinates (A_i, B_i) and (C_i, D_i).
Some line segments may overlap, in which case he needs to print the overlapping parts for each line segment separately.

What is the minimum number of seconds required to complete printing all the line segments when he operates the printing machine optimally?

Constraints

  • All input values are integers.
  • 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 )

Input

The input is given from Standard Input in the following format:

N S T
A_1 B_1 C_1 D_1
\vdots
A_N B_N C_N D_N

Output

Print the answer.

Your output will be considered correct if the absolute or relative error from the true value does not exceed 10^{-6}.

Sample Input 1

3 2 1
1 3 2 1
0 2 0 0
3 0 2 0

Sample Output 1

6.44317475868633722080
  • Emit the laser while moving the laser position from (0,0) to (0,2), printing the second line segment.
    • This takes 2 seconds.
  • Move the laser position from (0,2) to (1,3) without emitting the laser.
    • This takes \sqrt{2}/2 seconds.
  • Emit the laser while moving the laser position from (1,3) to (2,1), printing the first line segment.
    • This takes \sqrt{5} seconds.
  • Move the laser position from (2,1) to (2,0) without emitting the laser.
    • This takes 1/2 second.
  • Emit the laser while moving the laser position from (2,0) to (3,0), printing the third line segment.
    • This takes 1 second.
  • The total time taken is 2 + (\sqrt{2}/2) + \sqrt{5} + (1/2) + 1 \approx 6.443175 seconds.

Sample Input 2

2 1 1
0 0 10 10
0 2 2 0

Sample Output 2

20.97056274847714058517

Sample Input 3

6 3 2
-1000 -1000 1000 1000
1000 -1000 -1000 1000
-1000 -1000 1000 1000
1000 -1000 -1000 1000
1000 1000 -1000 -1000
-1000 1000 1000 -1000

Sample Output 3

9623.35256169626864153344

Multiple line segments overlap here, and you need to print the overlapping parts for each line segment separately.

Sample Input 4

6 10 8
1000 1000 -1000 -1000
1000 -1000 -1000 -1000
-1000 1000 1000 1000
-1000 1000 -1000 -1000
1000 1000 1000 -1000
1000 -1000 -1000 1000

Sample Output 4

2048.52813742385702910909