기둥을 돌아가는 최단 경로
시간 제한3초메모리 제한256 MB
반지름 100인 원반 로봇이 최대 8개의 기둥과 100 이상 거리를 유지하며 원점에서 목표점까지 가는 최단 경로 길이를 구합니다.
문제
로봇 대회에 참가한다. 대회에서는 평평한 경기장에 놓인 원판 모양 로봇을 준다. 경기장에는 기둥이 몇 개 서 있다. 로봇은 어느 방향으로든 움직이지만 기둥을 통과하지는 못한다. 기둥에 닿은 채로 그 둘레를 돌아 방향을 바꾸는 것은 할 수 있다.
로봇이 목표 지점에 도달하는 최단 경로의 길이를 구하라. 경로의 길이는 로봇 중심이 움직인 거리로 잰다. 로봇의 반지름은 이고 기둥의 굵기는 무시한다. 따라서 로봇 중심은 모든 기둥에서 항상 거리 이상 떨어져 있다. 거리가 정확히 인 위치는 지나갈 수 있다. 두 기둥의 간격이 로봇의 지름보다 좁으면 로봇은 그 사이를 빠져나가지 못한다.
입력
입력은 테스트 케이스 하나로 이루어진다.
N Gx Gy
x1 y1
...
xN yN
첫째 줄에 정수 세 개가 주어진다. 은 기둥의 개수이고 이다. 는 목표 지점이다. 로봇은 중심이 인 상태에서 출발하고, 중심이 에 닿으면 임무를 끝낸다. 출발 지점과 목표 지점은 서로 다르다.
이어지는 개의 줄에 각각 정수 두 개가 주어진다. 는 번째 기둥이 서 있는 위치다. 모든 좌표는 을 만족한다. 출발 지점과 목표 지점에서 거리 안에는 기둥이 없다. 인 번째 기둥과 번째 기둥 사이의 거리 는 또는 를 만족한다.
출력
목표 지점까지 가는 최단 경로의 길이를 소수점 아래 다섯째 자리까지 반올림해 한 줄에 출력한다. 목표 지점에 도달할 수 없으면 0.00000을 출력한다.