AT_agc019_c.[AGC019C] Fountain Walk

都市 Nevermore 有 $10^8$ 条东西向的街道和 $10^8$ 条南北向的街道，所有街道都标号为 $0$ 到 $10^8-1$。任意相邻两条东西向街道间的距离恰好为 $100$ 米，任意相邻两条南北向街道间的距离也恰好为 $100$ 米。

所有东西向街道与所有南北向街道都相互交叉。每个交叉点可用其所在的南北向街道编号 $x$ 和东西向街道编号 $y$ 来表示，记为点 $(x,\ y)$。

该城市内有 $N$ 个喷泉，分别设置在交叉点 $(X_i,\ Y_i)$。与普通的交叉点不同，这些交叉点上以交点为圆心画有半径为 $10$ 米的圆，作为喷泉的外周，圆内没有道路。

下图显示了城市一角的街道和喷泉的示例场景：

市长们决定，在同一条街道上行走时不希望多次经过喷泉。因此，任意一条东西向街道上至多只会有一个喷泉，南北向街道也是如此。

市民只能在东西向、南北向的街道及喷泉的外周上通行。请计算从交叉点 $(x_1,\ y_1)$ 移动到 $(x_2,\ y_2)$ 所需步行的最短距离（单位：米）。

输入以如下格式从标准输入读入。

$x_1$ $y_1$ $x_2$ $y_2$ $N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $:$ $X_N$ $Y_N$

输出从交叉点 $(x_1,\ y_1)$ 移动到 $(x_2,\ y_2)$ 所需步行的最短距离（单位为米）。若输出的绝对误差或相对误差不超过 $10^{-11}$，即可被认为是正确答案。

限制条件

• $0 \leq x_1, y_1, x_2, y_2 < 10^8$
• $1 \leq N \leq 200,\!000$
• $0 \leq X_i, Y_i < 10^8$
• 当 $i \neq j$ 时 $X_i \neq X_j$
• 当 $i \neq j$ 时 $Y_i \neq Y_j$
• $(x_1, y_1)$、$(x_2, y_2)$ 不相同，且这些点上没有喷泉。
• 所有输入为整数。

样例解释 1

下图给出了其中一条最短路径。起点为蓝点，终点为紫点，红线为途中路径。

样例解释 2

样例解释 3

由 ChatGPT 5 翻译