[ABC374] D - Laser Marking

D - Laser Marking

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 350 分

题面

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

• 在开始打印时，激光位置在坐标 处。

• 打印线段时，需按照以下步骤进行：

  • 首先，将激光位置移动到线段的端点之一。
    • 可从任一端点开始绘制。
  • 然后，将激光位置沿着从当前端点到另一个端点的直线移动，同时发射激光。
    • 不允许在线段中途停止打印。

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

• 当发射激光时，激光位置可以以每秒 个单位的速度沿正在打印的线段移动。

• 移动激光位置以外的操作所需的时间可以忽略不计。

高桥想要使用这台打印机打印 条线段。
第 条线段连接坐标点 和 。
一些线段可能会重叠，这种情况下，他需要分别打印每条线段的重叠部分。

在操作打印机时，完成打印所有线段需要的最短时间是多少？

限制条件

• 所有输入值均为整数。
• （）

---

输入

输入以以下格式从标准输入中给出：

输出

输出答案。

如果你的输出与正确值的绝对或相对误差不超过 ，则输出将被视为正确。

---

示例输入 1

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

示例输出 1

6.44317475868633722080

• 在打印第二条线段时，激光从 移动到 并发射激光。
  • 这需要 秒。
• 不发射激光，将激光位置从 移动到 。
  • 这需要 秒。
• 在打印第一条线段时，激光从 移动到 并发射激光。
  • 这需要 秒。
• 不发射激光，将激光位置从 移动到 。
  • 这需要 秒。
• 在打印第三条线段时，激光从 移动到 并发射激光。
  • 这需要 秒。
• 总共所需时间是 秒。

---

示例输入 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