가까스로 집에 도착하기

시간 제한2초메모리 제한512 MB

요약

최대 25개의 원 내부와 경계에서만 움직일 수 있을 때 두 점 사이 최단 경로의 길이를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 최단 경로, 기하, 완전 탐색
정답자: 아직 제출이 없습니다

문제

북극곰 바니가 신나게 돌아다니다가 정신을 차려 보니, 엄마에게서 너무 멀리 떨어진 얼음판 위에 혼자 서 있다. 멀리 엄마가 보이기는 하지만 돌아가려면 다른 얼음판을 밟고 건너는 수밖에 없다. 얼음판은 모두 완벽한 원 모양이다. 바니는 헤엄을 칠 줄 몰라서 얼음판이 덮고 있는 지점 위로만 움직인다. 엄마는 아들의 소동에 조금 지쳐서, 스스로 해결할 때까지 기다리기로 했다. 바니가 엄마와 만나려면 최소 얼마나 이동해야 하는지 구한다. 바니는 갈 길이 급하다.

입력

첫째 줄에 정수 네 개 $x_b$ , $y_b$ , $x_m$ , $y_m$ 이 주어진다 ( $-10^6 \le x_b, y_b, x_m, y_m \le 10^6$ ). $(x_b, y_b)$ 는 바니가 있는 위치, $(x_m, y_m)$ 은 엄마가 기다리는 위치다.
둘째 줄에 얼음판의 개수 $n$ 이 주어진다 ( $1 \le n \le 25$ ).
이어지는 $n$ 개 줄에 정수 세 개 $x_i$ , $y_i$ , $r_i$ 가 주어진다 ( $-10^6 \le x_i, y_i \le 10^6$ , $1 \le r_i \le 10^6$ ). $i$ 번째 얼음판은 중심 $(x_i, y_i)$ 에서 거리가 $r_i$ 이하인 모든 점으로 이루어진다.

출발할 때 두 곰은 모두 얼음판 위에 있다. 얼음판끼리 한 점에서 맞닿거나 서로 겹칠 수 있다.

출력

바니가 엄마와 만나기까지 이동해야 하는 최소 거리를 소수점 아래 여섯 자리로 반올림해 한 줄에 출력한다. 값이 딱 떨어지더라도 소수점 아래 여섯 자리를 모두 적는다.

엄마에게 갈 방법이 없으면 대신 impossible을 출력한다. 이때 바니의 안위는 걱정하지 않아도 된다. 엄마가 헤엄쳐 와서 구해 준다.

힌트

세 번째 예제 입력을 그린 그림이다. 초록 점이 바니, 빨간 점이 엄마의 위치다.

예제3

예제 1
입력
```
0 0 6 0
2
1 1 2
5 1 2
```
예상 출력
```
6.324555
```
예제 2
입력
```
0 0 7 0
2
1 1 2
6 1 2
```
예상 출력
```
impossible
```
예제 3
입력
```
0 0 1 3
3
0 -1 2
4 -1 3
2 3 2
```
예상 출력
```
4.269335
```