分数: 900 点
问题陈述
在Nevermore市,有 10^8 街道和 10^8 大道,编号均从 0 to 10^8-1。 所有的街道都是从西向东笔直延伸,所有的大道都是从南向北笔直延伸。 相邻街道之间和相邻大道之间的距离恰好是 100 米。
每条街道都与每条大道相交。每个交集都可以用对来描述 (x, y),其中 x 是大道 ID, y 是街道 ID。
有 N 城市中的喷泉,位于十字路口 (X_i, Y_i)。 与普通的交叉路口不同,这里有一个半径为圆的圆 10 米以交叉路口为中心,并且该圆内没有道路部分。
下图显示了城市中拥有道路和喷泉的部分的外观示例。
城市管理者不喜欢在沿着同一条道路移动时遇到多个喷泉。 因此,每条街道上最多有一个喷泉,每条大道也是如此。
公民可以沿着街道、大道和喷泉周边移动。 从交叉路口到达需要经过的最短距离是多少 (x_1, y_1) 到交叉路口 (x_2, y_2)?
约束
- 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
- X_i \neq X_j 为 i \neq j
- Y_i \neq Y_j 为 i \neq j
- 交叉路口 (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}.
示例输入 1
1 1 6 5 3 3 2 5 3 2 4
示例输出 1
891.415926535897938
下图显示了一种可能的最短路径。路径从蓝点开始,在紫色点结束,然后沿着红线行驶。
示例输入 2
3 5 6 4 3 3 2 5 3 2 4
示例输出 2
400.000000000000000
示例输入 3
4 2 2 2 3 3 2 5 3 2 4
示例输出 3
211.415926535897938