Informatica Online Judge

  분수 마을 [1958 / 07A6]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 3   Total Tried : 3


The Champion of this Problem (C++) : gs17100 - 0ms / 1355byte
My Best Submission (C++) : N/A

[AtCoder]

Background

경곽이는 분수마을에 살고 있다.

분수마을은 $10^8$행과 $10^8$열로 구성된 격자마을이다.

임의의 한 교차로에서 다음 교차로까지 한 블럭의 거리는 정확하게 $100m$이다.

이 마을에는 $N$개의 분수가 존재한다.

각 분수들은 원형이며 그 중심은 항상 격자의 교차로 상에 위치한다.

모든 분수의 반지름은 $10m$이다.

다음 그림은 3개의 분수를 가지는 모습을 나타낸다.



분수는 같은 행과 같은 열에 2개 이상 설치된 경우는 없다.

경곽이는 어떤 교차점 $(x_1, y_1)$에서 출발하여 교차점 $(x_2, y_2)$까지 최단 경로로 이동하려고 한다.

최단 거리를 구하는 프로그램을 작성하시오.

단, 출발점과 도착점은 서로 다르며, 출발점과 도착점에는 분수가 존재하지 않음이 보장된다.

그리고 임의의 교차점을 지나고자 할 때 그 교차점에 분수가 존재한다면 교차점으로 진입할 수 없고 분수의 원주를 따라서 이동해야만 한다.

Input

${x_1}~{y_1}~{x_2}~{y_2}~$

$N$

${X_1}~{Y_1}$

${X_2}~{Y_2}$

$:$

${X_N}~{Y_N}$

[입력값의 정의역]
$0≤x_1,y1,x2,y2<10^8$
$1≤N≤200,000$
$0≤X_i, Y_i<10^8$
$i≠j$일 때, $X_i≠X_j$
$i≠j$일 때, $Y_i≠Y_j$
모든 값은 정수이다.

Output

최단 경로로 이동한 거리를 출력한다.
단 절대 또는 상대오차는 $10^{-6}$이내이면 정답처리된다.

IO Example

입력
1 1 6 5
3
3 2
5 3
2 4

출력
891.415926535897938

* 설명

다음과 같이 이동하면 된다.



입력2
4 2 2 2
3
3 2
5 3
2 4

출력2
211.415926535897938

* 설명 : 다음과 같이 이동하면 된다.



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]