← 返回题目列表

AtCoder · icpc2015summer_day4_h

H. 激光切割机

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

问题陈述

Ciel 要做木工。 夏尔想要使用激光切割机在木板上进行切割。

为了简单起见,我们假设棋盘是一个二维平面。 木板上有几个部分,夏尔想沿着这些部分切割木板。 每个片段都有一个方向,夏尔必须沿着它们的方向切割这些片段。 当忽略方向时,这些线段是相连的,即线段上的任意两点都由线段直接或间接连接。

当激光切割机通电时,它会发射激光,击中电路板的一点并沿着其轨迹切割电路板。 激光最初指向 $(x, y)$。 Ciel可以进行以下两种操作:

  • 在电源打开的情况下移动激光切割机并沿其方向切割(一部分)一段,或
  • 在电源关闭的情况下将激光切割机移动到任意位置。 Ciel 不必一次切割整个片段;她可以在片段上的任意点开始或停止切割片段。

Ciel 喜欢高效,所以她想知道激光切割机切割所有片段的全部部分然后返回到初始点的最短路线。 您的任务是编写一个程序来计算激光切割机的最小总移动距离。


输入

输入的第一行包含一个整数 $n$ ($1 \leq n \leq 300$),即段数。 下一行包含两个整数 $x$ 和 $y$ ($-1{,}000 \leq x, y \leq 1{,}000$),这是激光的初始位置 $(x, y)$。 以下 $n$ 行的第 $i$ 行包含四个整数 $sx_i$、$sy_i$、$tx_i$ 和 $ty_i$ ($-1{,}000 \leq sx_i, sy_i, tx_i, ty_i \leq 1{,}000$), 这表明它们是第$i$段的端点,并且激光切割机可以沿着从$(sx_i,sy_i)$到$(tx_i,ty_i)$的方向切割板。 输入满足以下条件: 对于所有 $i$ ($1 \leq i \leq n$),$(sx_i, sy_i) \neq (tx_i, ty_i)$。 初始点 $(x, y)$ 位于至少一个给定线段上。 对于所有不同的 $i, j$ ($1 \leq i, j \leq n$),第 $i$ 段和第 $j$ 段最多共享一个点。

输出

输出一条线,其中包含激光切割机切割所有线段并移回初始点所需移动的最小总移动距离。绝对误差或相对误差应小于$10^{-6}$。


示例输入 1

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

样本输入 1 的输出

6.0000000000000000

示例输入 2

2
0 1
0 0 0 2
-1 1 1 1

样本输入 2 的输出

6.8284271247461900

示例输入 3

5
0 0
0 0 1 0
1 1 -1 1
-1 1 -1 -1
-1 -1 1 -1
1 -1 1 1

样本输入 3 的输出

10.0000000000000000