This page is still under construction.

Parts of this page are still being built. What you see may change.

Cornering at Poles

Time limit3sMemory limit256 MB

Summary
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 100100 and the thickness of a pole is ignored, so the center of the robot always stays at distance 100100 or more from every pole. A position where that distance is exactly 100100 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. NN is the number of poles, with 1≤N≤81 \le N \le 8. (Gx,Gy)(G_x, G_y) is the goal position. The robot starts with its center at (0,0)(0, 0) and finishes when its center reaches (Gx,Gy)(G_x, G_y). The starting position and the goal position are different.

Each of the next NN lines has two integers. (xi,yi)(x_i, y_i) is the position of the ii-th pole. Every coordinate satisfies −1000≤Gx,Gy,xi,yi≤1000-1000 \le G_x, G_y, x_i, y_i \le 1000. No pole stands within distance 100.01100.01 of the starting position or of the goal position. For the distance di,jd_{i,j} between the ii-th pole and the jj-th pole with i≠ji \ne j, either 1≤di,j<199.991 \le d_{i,j} < 199.99 or 200.01<di,j200.01 < d_{i,j} 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.

Examples7

  1. Example 1

    Input
    8 900 0
    40 100
    70 -80
    350 30
    680 -20
    230 230
    300 400
    530 130
    75 -275
    
    Expected output
    1210.99416
    
  2. Example 2

    Input
    1 0 200
    120 0
    
    Expected output
    200.00000
    
  3. Example 3

    Input
    3 110 110
    0 110
    110 0
    200 10
    
    Expected output
    476.95048
    
  4. Example 4

    Input
    4 0 200
    90 90
    -90 90
    -90 -90
    90 -90
    
    Expected output
    0.00000
    
  5. Example 5

    Input
    2 0 -210
    20 -105
    -5 -105
    
    Expected output
    325.81116
    
  6. Example 6

    Input
    8 680 -50
    80 80
    80 -100
    480 -120
    -80 -110
    240 -90
    -80 100
    -270 100
    -420 -20
    
    Expected output
    1223.53071
    
  7. Example 7

    Input
    2 -1 600
    -99 300
    -100 540
    
    Expected output
    600.01216