配点 : $900$ 点

問題文

都市ネバーモアには、$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)$ に移動するには、最短で何メートル歩く必要があるでしょうか？

制約

• $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)$ は異なり、これらの位置に噴水は設置されていない。
• 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$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 6 5
3
3 2
5 3
2 4

891.415926535897938

最短経路の一つを下の図に示します。スタート地点は青の点、ゴール地点は紫の点、途中経路は赤の線です。

3 5 6 4
3
3 2
5 3
2 4

400.000000000000000

4 2 2 2
3
3 2
5 3
2 4

211.415926535897938