기둥을 돌아가는 최단 경로

아직 제출이 없습니다시간 제한3초메모리 제한256 MB

문제

로봇 대회에 참가한다. 대회에서는 평평한 경기장에 놓인 원판 모양 로봇을 준다. 경기장에는 기둥이 몇 개 서 있다. 로봇은 어느 방향으로든 움직이지만 기둥을 통과하지는 못한다. 기둥에 닿은 채로 그 둘레를 돌아 방향을 바꾸는 것은 할 수 있다.

로봇이 목표 지점에 도달하는 최단 경로의 길이를 구하라. 경로의 길이는 로봇 중심이 움직인 거리로 잰다. 로봇의 반지름은 100100이고 기둥의 굵기는 무시한다. 따라서 로봇 중심은 모든 기둥에서 항상 거리 100100 이상 떨어져 있다. 거리가 정확히 100100인 위치는 지나갈 수 있다. 두 기둥의 간격이 로봇의 지름보다 좁으면 로봇은 그 사이를 빠져나가지 못한다.

입력

입력은 테스트 케이스 하나로 이루어진다.

N Gx Gy
x1 y1
...
xN yN

첫째 줄에 정수 세 개가 주어진다. NN은 기둥의 개수이고 1N81 \le N \le 8이다. (Gx,Gy)(G_x, G_y)는 목표 지점이다. 로봇은 중심이 (0,0)(0, 0)인 상태에서 출발하고, 중심이 (Gx,Gy)(G_x, G_y)에 닿으면 임무를 끝낸다. 출발 지점과 목표 지점은 서로 다르다.

이어지는 NN개의 줄에 각각 정수 두 개가 주어진다. (xi,yi)(x_i, y_i)ii번째 기둥이 서 있는 위치다. 모든 좌표는 1000Gx,Gy,xi,yi1000-1000 \le G_x, G_y, x_i, y_i \le 1000을 만족한다. 출발 지점과 목표 지점에서 거리 100.01100.01 안에는 기둥이 없다. iji \ne jii번째 기둥과 jj번째 기둥 사이의 거리 di,jd_{i,j}1di,j<199.991 \le d_{i,j} < 199.99 또는 200.01<di,j200.01 < d_{i,j}를 만족한다.

출력

목표 지점까지 가는 최단 경로의 길이를 소수점 아래 다섯째 자리까지 반올림해 한 줄에 출력한다. 목표 지점에 도달할 수 없으면 0.00000을 출력한다.