AT_abc374_d [ABC374D] Laser Marking

在 $xy$ 平面上，有一台可以边照射激光边打印线段的打印机。 - 打印开始时，激光照射位置在坐标 $(0, 0)$。 - 打印一条线段时，按照以下流程进行： - 首先，将激光照射位置移动到该线段的两个端点中的任意一个。 - 可以从任意一个端点开始绘制。 - 然后，从当前端点沿着线段一直照射激光并移动到另一个端点。 - 不允许在打印线段的过程中中止打印。 - 未照射激光时，激光照射位置可以以每秒 $S$ 的速度向任意方向移动。 - 照射激光时，激光照射位置只能沿正在打印的线段以每秒 $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 \leq N \leq 6$ - $1 \leq T \leq S \leq 1000$ - $-1000 \leq A_i, B_i, C_i, D_i \leq 1000$ - $(A_i, B_i) \neq (C_i, D_i)$（$1 \leq i \leq N$） ### 样例解释 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$ 秒。 ### 样例解释 3 虽然有多条线段重叠，但每条线段都需要单独打印其重叠部分。 由 ChatGPT 4.1 翻译