← 返回题目列表

AtCoder · abc374_d

G. 激光打标

中文机器翻译题面 查看原题

分数: 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