103743: [Atcoder]ABC374 D - Laser Marking

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

问题陈述

有一台印刷机可以在 $xy$ 平面上通过发射激光来打印线段。

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

• 在打印线段时，遵循以下步骤。

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

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

• 当发射激光时，激光位置可以以 $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$ 秒。
• 在没有发射激光的情况下，将激光位置从 $(0,2)$ 移动到 $(1,3)$。
  • 这需要 $\sqrt{2}/2$ 秒。
• 在将激光位置从 $(1,3)$ 移动到 $(2,1)$ 的同时发射激光，打印第一条线段。
  • 这需要 $\sqrt{5}$ 秒。
• 在没有发射激光的情况下，将激光位置从 $(2,1)$ 移动到 $(2,0)$。
  • 这需要 $1/2$ 秒。
• 在将激光位置从 $(2,0)$ 移动到 $(3,0)$ 的同时发射激光，打印第三条线段。
  • 这需要 $1$ 秒。
• 总共花费的时间是 $2 + (\sqrt{2}/2) + \sqrt{5} + (1/2) + 1 \approx 6.443175