Score : $350$ points

问题陈述

有一台打印机器，通过发射激光在$xy$平面上打印线段。

• 开始打印时，激光位置在坐标$(0, 0)$。

• 打印线段时，遵循以下程序。

  • 首先，将激光位置移动到线段的一个端点。
    • 可以从任一端点开始绘制。
  • 然后，从当前端点直线移动激光位置到另一个端点，同时发射激光。
    • 不允许在线段中间停止打印。

• 不发射激光时，激光位置可以以每秒$S$单位的速度向任何方向移动。

• 发射激光时，激光位置可以以每秒$T$单位的速度沿着正在打印的线段移动。

• 除了移动激光位置之外的操作所需的时间可以忽略。

高桥想要使用这台打印机器打印$N$个线段。 第$i$个线段连接坐标$(A_i, B_i)$和$(C_i, D_i)$。 一些线段可能会重叠，在这种情况下，他需要分别打印每个线段的重叠部分。

当他以最佳方式操作打印机器时，完成打印所有线段所需的最短时间是多少？

以上为大语言模型 kimi 翻译，仅供参考。

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