[普及] 激光枪

有一台印刷机，它可以在发射激光束的同时在 $xy$ 平面上印刷一条线段。

• 打印开始时，激光照射位置位于坐标 $(0,\ 0)$。

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

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

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

• 当激光照射时，激光照射位置可以以每秒 $T$ 的速度沿打印线段移动。

• 除了移动激光照射位置所需的时间外，其他所需的时间可以忽略不计。

现在希望用这台打印机打印 $N$ 条线段。 第 i 个线段连接坐标 $(A_i,\ B_i)$ 和 $(C_i,\ D_i)$。 请注意，有几条线段可能会重叠，但每次都必须打印所有线段的重叠部分。

当成功操作打印机时，完成打印所有线段所需的最短时间是多少？

输入格式

第一行为 $3$ 个整数 $N, \ S, \ T$。

接下来 $N$ 行，每行包含 $A_i,\ B_i, \ C_i, \ D_i$

输出格式

输出答案。 请注意，如果与真实值的绝对或相对误差小于 $10^{-6}$，答案将被视为正确答案。

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

6.44317475868633722080

2 1 1
0 0 10 10
0 2 2 0

20.97056274847714058517

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 1000 -1000

9623.35256169626864153344

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 -1000 -1000 -1000 1000

2048.52813742385702910909

提示

【样例 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$ 大约 $6.443175$ 秒。

【样例 3 解释】

• 有几个重叠的线段，但每次都需要打印所有线段的重叠部分。

【数据范围】

• 所有输入都是整数
• $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$ )

来源