Laser Marking

题目描述

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

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

当打印一条线段时，遵循以下过程。

首先，将激光位置移动到线段的一个端点。 可以从任一端点开始绘制。

然后，将激光位置沿直线从当前端点移动到另一端点，同时发射激光。 不允许在一条线段的中间停止打印。

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

当发射激光时，激光位置可以沿正在打印的线段以每秒 $T$ 个单位的速度移动。 除移动激光位置之外的操作所需时间可以忽略。

Takahashi 想使用这台打印机打印 $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}$，则认为是正确的。

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

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

2048.52813742385702910909

提示

所有输入值均为整数。 $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$ )在从 $(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$ 秒。
这里有多条线段重叠，你需要为每一条线段分别打印重叠部分。

标签: AtCoder|abc374D

来源

AtCoder|abc374D