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

输入 #1

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

输出 #1

6.44317475868633722080

输入输出样例 #2

输入 #2

2 1 1
0 0 10 10
0 2 2 0

输出 #2

20.97056274847714058517

输入输出样例 #3

输入 #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

输入 #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

说明/提示

限制条件

• 所有输入均为整数。
• $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 翻译