4524: 「FJOI2018」邮递员问题

$2010$ 年以来，网购市场发展迅速，快递公司成为促成交易成功的关键环节。小郭是一名顺丰快递员，他的工资主要包括底薪、送货提成、收件提成、其他福利补贴等。 小郭每完成一件客户的快递单，一般能拿到运费 $10\%$ 的提成。因此小郭完成的快递单越多越快，他的收入就越高。 小郭负责城市中 $2$ 个平行街道的所有快递业务。在这 $2$ 个平行街道上有 $2$ 处快递工作站。 小郭每次投递的行程都是从一个工作站出发，完成所有快递单的投递后，回到另一个工作站。 为了高效地完成投递任务，小郭希望用最短的行程来完成所有快递单的投递任务。也就是说，对于给定的 $2$ 个平行街道的街距和 $2$ 个工作站位置，以及所有投递点的位置，小郭要计算从一个工作站出发，完成所有快递单的投递后，回到另一个工作站的最短行程。街距是指 $2$ 个平行街道的之间的垂直距离。如果设平面坐标系的 $x$ 轴与街道平行，且 $2$个平行街道上的最左端位置的 $x$ 坐标均为 $0$，则 $2$ 个平行街道上的任何位置可以用从街道最左端到该位置的直线距离，即该位置的 $x$ 坐标值来表示。 例如，设 $2$ 个平行街道 A 和 B 的街距是 $2$。$2$ 个工作站 $S_1$和 $S_2$ 的位置分别位于街道 A 的 $x=1$ 和街道 B 的 $x=3$ 处。另外有 $2$个投递点 $T_1$ 和 $T_2$ 的位置分别位于街道 A 的 $x=3$ 和街道 B 的 $x=1$ 处，如图所示。小郭的任务就是要从工作站 $S_1$ 出发，完成在 $T_1$ 和 $T_2$ 处的快递单投递后，回到另一个工作站 $S_2$。 **编程任务**：对于给定的 $2$ 个平行街道的街距和 $2$ 个工作站位置，以及所有投递点的位置，计算从一个工作站出发，完成所有快递单的投递后，回到另一个工作站的最短行程。

第 $1$ 行有 $2$ 个正整数 $n,m$，$1 \le n,m \le 10000$，分别表示 $2$ 个平行街道 A 和 B 上的位置数（包括投递点的位置和工作站的位置）。位置编号为 A：$1,2,\ldots,n$；B：$1,2,\ldots,m$。 第 $2$ 行有 $4$ 个正整数 $a,b,c,d$，表示 $2$ 个工作站位置分别为 $(a,b)$ 和 $(c,d)$。$a=0$ 或 $c=0$ 表示相应的工作站在街道 $A$，$a=1$ 或 $c=1$ 表示相应的工作站在街道 $B$。$b$ 和 $d$ 分别表示工作站在相应的街道的位置号。例如，若 $(a,b) = (0,3)$ 表示第 $1$ 个工作站位于街道 $A$ 上，其位置位于给出的街道 $A$ 的 $n$ 个位置的第 $3$ 个位置。 第 $3$ 行有 $1$ 个实数 $h$，表示 $2$ 个平行街道的街距（$1 \le h \le 10$）。 第 $4$ 行有 $n$ 个实数，表示街道 $A$ 上 $n$ 个位置的 $x$ 坐标（$1 \le x < 20000$）。 第 $5$ 行有 $m$ 个实数，表示街道 $B$ 上 $m$ 个位置的 $x$ 坐标（$1 \le x < 20000$）。

输出计算出的最短行程，保留 $2$ 位小数。

2 2
0 1 1 2
2
1 3
1 3

6.83