Problem: Example

Input

8 900 0
40 100
70 -80
350 30
680 -20
230 230
300 400
530 130
75 -275


Output

1210.99416

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define MAX 1000
#define inf 1<<29
#define linf (1e16)
#define eps (1e-7)
#define mod 1000000007
#define pi M_PI
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,int> pdi;
typedef vector<int> vi;
typedef vector<pii> vpi;

class Point{
public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y){}

  Point operator+(Point p){ return Point(x+p.x,y+p.y);}
  Point operator-(Point p){ return Point(x-p.x,y-p.y);}
  Point operator*(double k){ return Point(x*k,y*k);}
  Point operator/(double k){ return Point(x/k,y/k);}
  bool operator<(Point p)const{ return (x!=p.x ? x<p.x : y<p.y);}
  bool operator==(Point p)const{ return fabs(x-p.x)<eps && fabs(y-p.y)<eps;}

  double abs(){ return sqrt(norm());}
  double norm(){ return (x*x+y*y);}
};
typedef Point Vector;
typedef vector<Point> Polygon;

class Segment{
public:
  Point p1,p2;
  Segment(Point p1=Point(),Point p2=Point()):p1(p1),p2(p2){}
};
typedef Segment Line;

class Circle{
public:
  Point c;
  double r;
  Circle(Point c=Point(),double r=0.0):c(c),r(r){}
};

double norm(Vector a){ return (a.x*a.x+a.y*a.y);}
double abs(Vector a){ return sqrt(norm(a));}
double dot(Vector a,Vector b){ return (a.x*b.x+a.y*b.y);}
double cross(Vector a,Vector b){ return (a.x*b.y-a.y*b.x);}

double getDistanceLP(Line l,Point p){
  return abs(cross(l.p2-l.p1,p-l.p1)/abs(l.p2-l.p1));
}

double getDistanceSP(Segment s,Point p){
  if(dot(s.p2-s.p1,p-s.p1)<0.0)return abs(p-s.p1);
  if(dot(s.p1-s.p2,p-s.p2)<0.0)return abs(p-s.p2);
  return getDistanceLP(s,p);
}

bool intersect(Circle c,Segment s){
  if(getDistanceSP(s,c.c)-c.r<-eps)return true;
  return false;
}

bool intersect(Circle a,Circle b){
  if(abs(a.c-b.c)-(a.r+b.r)<eps)return true;
  return false;
}

bool in(Circle c,Point p){
  if(abs(c.c-p)-c.r<-eps)return true;
  return false;
}

double arg(Vector p){ return atan2(p.y,p.x);}
Vector polar(double a,double r){ return Point(cos(r)*a,sin(r)*a);}

pair<Point,Point> getCrossPoints(Circle c1,Circle c2){
  double d=abs(c1.c-c2.c);
  double a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
  double t=arg(c2.c-c1.c);
  return mp(c1.c+polar(c1.r,t+a),c1.c+polar(c1.r,t-a));
}

double getAngle(Vector a,Vector b){
  double tmp=dot(a,b)/(abs(a)*abs(b));
  if(tmp<-1.0)tmp=-1.0;
  if(1.0<tmp)tmp=1.0;
  double r=acos(tmp)*180.0/pi;
  if(cross(a,b)<-eps)r=360.0-r;
  return r;
}

Point rotate(Point base,Point a,double r){
  Point b=a-base;
  a.x=b.x*cos((r/180)*M_PI)-b.y*sin((r/180)*M_PI);
  a.y=b.x*sin((r/180)*M_PI)+b.y*cos((r/180)*M_PI);
  a=a+base;
  return a;
}

pair<Point,Point> getTangent(Circle c,Point p){
  Vector v=p-c.c;
  double r=acos(c.r/abs(v))*360/(2*pi);
  v=v*c.r/abs(v);
  Point p1=rotate(c.c,c.c+v,r);
  Point p2=rotate(c.c,c.c+v,360-r);
  return mp(p1,p2);
}

vector<Line> getCommonTangent(Circle a,Circle b){
  vector<Line> vp;

  double d=abs(b.c-a.c),c,s;
  Vector v=(b.c-a.c)/d,v1=v*a.r,v2=v*b.r;
  Point p1,p2;

  c=sqrt(d*d-(a.r-b.r)*(a.r-b.r));
  s=(180*asin(c/d))/pi;

  if(a.r<b.r){
    vp.push_back(Line(rotate(a.c,a.c+v1,180-s),rotate(b.c,b.c-v2,360-s)));
    vp.push_back(Line(rotate(a.c,a.c+v1,180+s),rotate(b.c,b.c-v2,s)));
  }
  else {
    vp.push_back(Line(rotate(a.c,a.c+v1,s),rotate(b.c,b.c-v2,180+s)));
    vp.push_back(Line(rotate(a.c,a.c+v1,360-s),rotate(b.c,b.c-v2,180-s)));
  }
  if(intersect(a,b))return vp;
  
  c=sqrt(d*d-(a.r+b.r)*(a.r+b.r));
  s=(180*asin(c/d))/pi;
  
  vp.push_back(Line(rotate(a.c,a.c+v1,s),rotate(b.c,b.c-v2,s)));
  vp.push_back(Line(rotate(a.c,a.c+v1,360-s),rotate(b.c,b.c-v2,360-s)));
  
  return vp;
}

int n;
Point s(0,0),g;
vector<Circle> vc;
vector<pair<Point,int> > vp;
vector<vector<pdi> > e;

void add_edge(int from,int to,double cost){
  e[from].pb(mp(cost,to));
  e[to].pb(mp(cost,from));
}

void make(){
  vp.pb(mp(s,-1));
  vp.pb(mp(g,-2));
  FOR(i,0,n){
    pair<Point,Point> vpp=getTangent(vc[i],s);
    bool flag=true;
    FOR(j,0,n)if(in(vc[j],vpp.f))flag=false;
    if(flag)vp.pb(mp(vpp.f,i));
    flag=true; 
    FOR(j,0,n)if(in(vc[j],vpp.s))flag=false;
    if(flag)vp.pb(mp(vpp.s,i));

    vpp=getTangent(vc[i],g);
    flag=true;
    FOR(j,0,n)if(in(vc[j],vpp.f))flag=false;
    if(flag)vp.pb(mp(vpp.f,i));
    flag=true; 
    FOR(j,0,n)if(in(vc[j],vpp.s))flag=false;
    if(flag)vp.pb(mp(vpp.s,i));
  }
  FOR(i,0,n){
    FOR(j,i+1,n){
      vector<Segment> vs=getCommonTangent(vc[i],vc[j]);
      FOR(k,0,vs.size()){
        vp.pb(mp(vs[k].p1,i));
        vp.pb(mp(vs[k].p2,j));
      }
    }
  }
  vector<vector<Point> > vcp(n);
  FOR(i,0,n){
    FOR(j,0,n){
      if(i==j)continue;
      if(intersect(vc[i],vc[j])){
        pair<Point,Point> pp=getCrossPoints(vc[i],vc[j]);
        vcp[i].pb(pp.f);
        vcp[i].pb(pp.s);
      }
    }
  }
  e.resize(vp.size());
  FOR(i,0,vp.size()){
    FOR(j,i+1,vp.size()){
      if(vp[i].s==vp[j].s){
        double dis=linf;
        bool flag=true;
        int ind=vp[i].s;
        Vector a=(vp[i].f-vc[ind].c),b=(vp[j].f-vc[ind].c);
        double ang=getAngle(a,b);
        FOR(k,0,vcp[ind].size()){
          Vector v=vcp[ind][k]-vc[ind].c;
          if(getAngle(a,v)-ang<-eps)flag=false;
        }
        if(flag)dis=min(dis,2*vc[ind].r*pi*(ang/360.0));
        flag=true;
        ang=getAngle(b,a);
        FOR(k,0,vcp[ind].size()){
          Vector v=vcp[ind][k]-vc[ind].c;
          if(getAngle(b,v)-ang<-eps)flag=false;
        }
        if(flag)dis=min(dis,2*vc[ind].r*pi*(ang/360.0));
        if(dis!=inf)add_edge(i,j,dis);
      }
      else {
        bool flag=true;
        FOR(k,0,n)if(intersect(vc[k],Segment(vp[i].f,vp[j].f)))flag=false;
        if(flag)add_edge(i,j,abs(vp[i].f-vp[j].f));
      }
    }
  }
  return;
}

double dijkstra(){
  double d[MAX];
  fill(d,d+MAX,linf);
  priority_queue<pdi,vector<pdi>,greater<pdi> > pq;
  d[0]=0;
  pq.push(mp(0,0));

  while(pq.size()){
    pdi u=pq.top();
    pq.pop();

    if(d[u.s]-u.f<-eps)continue;

    FOR(i,0,e[u.s].size()){
      int next=e[u.s][i].s;
      double cost=e[u.s][i].f;
      if(u.f+cost-d[next]<-eps){
        d[next]=u.f+cost;
        pq.push(mp(d[next],next));
      }
    }
  }
  if(d[1]==linf)return 0.0;
  return d[1];
}

int main()
{
  cin>>n;
  cin>>g.x>>g.y;
  FOR(i,0,n){
    int x,y;
    cin>>x>>y;
    vc.pb(Circle(Point(x,y),100));
  }
  make();
  pd(dijkstra());
  return 0;
}