← 返回题目列表

AtCoder · agc019_c

C. 喷泉步道

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

分数: 900 点

问题陈述

在Nevermore市,有 10^8 街道和 10^8 大道,编号均从 0 to 10^8-1。 所有的街道都是从西向东笔直延伸,所有的大道都是从南向北笔直延伸。 相邻街道之间和相邻大道之间的距离恰好是 100 米。

每条街道都与每条大道相交。每个交集都可以用对来描述 (x, y),其中 x 是大道 ID, y 是街道 ID。

有 N 城市中的喷泉,位于十字路口 (X_i, Y_i)。 与普通的交叉路口不同,这里有一个半径为圆的圆 10 米以交叉路口为中心,并且该圆内没有道路部分。

下图显示了城市中拥有道路和喷泉的部分的外观示例。

1f931bf0c98ec6f07e612b0282cdb094.png

城市管理者不喜欢在沿着同一条道路移动时遇到多个喷泉。 因此,每条街道上最多有一个喷泉,每条大道也是如此。

公民可以沿着街道、大道和喷泉周边移动。 从交叉路口到达需要经过的最短距离是多少 (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

下图显示了一种可能的最短路径。路径从蓝点开始,在紫色点结束,然后沿着红线行驶。

c49e52b9b79003f61b8a6efa5dad8ba3.png

示例输入 2

3 5 6 4
3
3 2
5 3
2 4

示例输出 2

400.000000000000000
f9090ab734c89424c413f3b583376990.png

示例输入 3

4 2 2 2
3
3 2
5 3
2 4

示例输出 3

211.415926535897938
4b76416161f27cad20333a9ac636e00f.png