Cornering at Poles
Time limit3sMemory limit256 MB
Guide a disc robot of radius 100 from the origin to the goal along the shortest path that stays clear of up to eight pole obstacles.
- Level
Medium7 of 10
- Topics
- Geometry, Shortest path, Graph
- Solved
- No attempts yet
Problem
You are competing in a robot contest. The contest gives you a disc shaped robot placed on a flat field, and several poles stand on that field. The robot moves in any direction but cannot pass through a pole. It can turn around a pole while touching it.
Find the length of the shortest path the robot takes to reach the goal. The length of the path is the distance travelled by the center of the robot. The radius of the robot is and the thickness of a pole is ignored, so the center of the robot always stays at distance or more from every pole. A position where that distance is exactly is allowed. When two poles are closer to each other than the diameter of the robot, the robot cannot pass between them.
Input
The input is a single test case.
N Gx Gy
x1 y1
...
xN yN
The first line has three integers. is the number of poles, with . is the goal position. The robot starts with its center at and finishes when its center reaches . The starting position and the goal position are different.
Each of the next lines has two integers. is the position of the -th pole. Every coordinate satisfies . No pole stands within distance of the starting position or of the goal position. For the distance between the -th pole and the -th pole with , either or holds.
Output
Print the length of the shortest path to the goal on one line, rounded to exactly five digits after the decimal point. If the robot cannot reach the goal, print 0.00000.