分数: 350 点
问题陈述
有一台打印机可以在纸上打印线段 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) to (0,2),打印第二条线段。
- 这需要 2 秒。
- 将激光位置从 (0,2) to (1,3) 不发射激光。
- 这需要 \sqrt{2}/2 秒。
- 发射激光,同时将激光位置从 (1,3) to (2,1),打印第一条线段。
- 这需要 \sqrt{5} 秒。
- 将激光位置从 (2,1) to (2,0) 不发射激光。
- 这需要 1/2 第二。
- 发射激光,同时将激光位置从 (2,0) to (3,0),打印第三行段。
- 这需要 1 第二。
- 花费的总时间是 2 + (\sqrt{2}/2) + \sqrt{5} + (1/2) + 1 \approx 6.443175 秒。
示例输入 2
2 1 1 0 0 10 10 0 2 2 0
示例输出 2
20.97056274847714058517
示例输入 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
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