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 EQ(a,b) (abs((a)-(b)) < EPS)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define sz size()
#define all(a) (a).begin(),(a).end()

using namespace std;
typedef long double D;
typedef complex<D> P;
typedef pair<P,P> L;
typedef pair<P,D> C;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<D,int> pdi;
typedef pdi edge;

const bool visual = false;

const D EPS = 1e-8;
const D INF = 1e15;
const D PI = acos(-1);

namespace std{
  bool operator<(const P &a,const P &b){
    return EQ(real(a),real(b))?imag(a)+EPS<imag(b):real(a)+EPS<real(b);
  }
  bool operator==(const P &a, const P &b){return EQ(a,b);}
}

inline P unit(P p){return p/abs(p);}
inline pair<P,P> normal(P p){return make_pair(p*P(0,1),p*P(0,-1));}
inline D dot(P x, P y){return real(conj(x)*y);}
inline D cross(P x, P y){return imag(conj(x)*y);}

//rotate a point counter-clockwise on the origin
inline P rotate(P v, D s){
  return P(real(v)*cos(s) - imag(v)*sin(s), real(v)*sin(s) + imag(v)*cos(s) );
}
inline D arg(D a,D b,D c){return acos( (b*b+c*c-a*a)/(2*b*c) );}

inline P line_cp(L a,L b){
  return a.fs+(a.sc-a.fs)*cross(b.sc-b.fs,b.fs-a.fs)/cross(b.sc-b.fs,a.sc-a.fs);
}

int ccw(P a,P b,P c){
  b -= a;c -= a;
  if (cross(b,c)>EPS) return 1;   //counter clockwise
  if (cross(b,c)<-EPS) return -1; //clockwise
  if (dot(b, c)<-EPS) return 2;   //c--a--b on line
  if (abs(b)+EPS<abs(c)) return -2;   //a--b--c on line
  return 0;                       //on segment
}

inline bool in_cir(C c,P x){return (abs(x-c.fs) +EPS < c.sc);}
inline bool on_cir(C c,P x){return EQ(abs(x-c.fs),c.sc);}

inline vector<P> cp_cir_to_line(C a, L l){
  vector<P> v;
  P n = normal(l.fs-l.sc).fs;
  P p = line_cp(l,L(a.fs,a.fs+n));

  if(on_cir(a,p))v.pb(p);
  else if(in_cir(a,p)){
    D d = abs(a.fs-p);
    D len = sqrt(a.sc*a.sc - d*d);
    P cp_vec = len * unit(l.fs-l.sc);
    v.pb(p + cp_vec);
    v.pb(p - cp_vec);
  }
  return v;
}

inline vector<L> adj_line(C c, P p){
  vector<L> res;
  P a = c.fs + c.sc * unit(p-c.fs);
  vector<P> b = cp_cir_to_line(C(c.fs,abs(c.fs-p)), L(a,a+normal(c.fs-p).fs));
  rep(i,b.sz)res.pb(L(p, c.fs + c.sc * unit(b[i]-c.fs)));
  return res;
}

inline vector<L> common_adj_line(C a,C b){
  vector<L> res;
  if(a.sc+EPS<b.sc)return common_adj_line(b,a);
  if(EQ(real(a.fs),real(b.fs)) && EQ(imag(a.fs),imag(b.fs)) && EQ(a.sc,b.sc))return res;

  P pos = (b.fs-a.fs)*a.sc/(a.sc+b.sc)+a.fs;
  if(!in_cir(a,pos))res = adj_line(a,pos);

  if(EQ(a.sc,b.sc)){
    pair<P,P> n = normal(unit(b.fs-a.fs)*a.sc);
    res.pb(L(a.fs+n.fs,b.fs+n.fs));
    res.pb(L(a.fs+n.sc,b.fs+n.sc)); 
  }else{
    pos = (b.fs-a.fs)*a.sc/(a.sc-b.sc) + a.fs;
    if(!in_cir(a,pos)){
      vector<L> tmp = adj_line(a,pos);
      rep(i,tmp.sz)res.pb(tmp[i]);
    }
  }
  return res;
}

inline int cpr(C a,C b){
  D d = abs(a.fs-b.fs);
  if(a.sc+b.sc + EPS < d)return -1;      //no cross point (outside)
  if(b.sc+d + EPS < a.sc)return 1;       //no cross point (inside,B in A)
  if(a.sc+d + EPS < b.sc)return 2;       //no cross point (inside,A in B)
  if(abs(a.sc+b.sc - d) < EPS)return -3; //one cross point (outside)
  if(abs(b.sc+d - a.sc) < EPS)return 3;  //one cross point (inside,B in A)
  if(abs(a.sc+d - b.sc) < EPS)return 4;  //one cross point (inside,A in B)
  return 0;                              //two cross point
}

inline vector<P> cp_cir_to_cir(C a, C b){
  vector<P> v;
  int pos = cpr(a,b);
  if(pos==0){
    D s = arg(b.sc,abs(b.fs-a.fs),a.sc);
    P x = a.sc * unit(b.fs - a.fs);
    v.pb(a.fs + rotate(x,s));
    v.pb(a.fs + rotate(x,-s));
  }else if(abs(pos) >= 3){
    v.pb(a.fs + a.sc * unit(b.fs-a.fs));
  }
  return v;
}

vector<L> remove_cross(vector<C> circles, vector<L> segs){
  vector<L> res;
  for(L l : segs){
    bool f = true;
    for(C c : circles){
      vector<P> cp = cp_cir_to_line(c,l);
      if(cp.sz<2)continue;
      for(P p : cp){
	if(ccw(l.fs,l.sc,p) == 0)f = false;
      }
      if(!f)break;
    }
    if(f)res.pb(l);
  }
  return res;
}

vector< vector<edge> > make_graph(vector<C> circles, vector<L> segs,
				  P start, P goal, int &vs, int &vg){
  vector<P> vertex;
  vertex.pb(start); vertex.pb(goal);

  for(L l : segs){
    bool f1 = true, f2 = true;
    for(C c : circles){
      if(in_cir(c,l.fs))f1 = false;
      if(in_cir(c,l.sc))f2 = false;
    }
    if(f1)vertex.pb(l.fs); if(f2)vertex.pb(l.sc);
  }

  rep(i,circles.sz)rep(j,i){
    vector<P> cp = cp_cir_to_cir(circles[i],circles[j]);
    for(P p : cp){
      bool f = true;
      for(C c : circles){
	if(in_cir(c,p))f = false;
      }
      if(f)vertex.pb(p);
    }
  }

  sort(all(vertex));
  vertex.erase(unique(all(vertex)),vertex.end());
  
  int n = vertex.sz;
  vector< vector<edge> > res(n);
  for(L l : segs){
    P mid = (l.fs+l.sc)/2.0L;
    bool f = true;
    for(C c : circles){
      if(in_cir(c,mid))f = false;
    }
    if(!f)continue;

    int a = lower_bound(all(vertex),l.fs) - vertex.begin();
    int b = lower_bound(all(vertex),l.sc) - vertex.begin();
    if(a==n || b==n)continue;

    D d = abs(l.fs-l.sc);
    res[a].pb(edge(d,b));
    res[b].pb(edge(d,a));
  }

  vi cross(n,0);
  vector< vector<pdi> > onC(circles.sz);
  rep(i,vertex.sz)rep(j,circles.sz){
    if(on_cir(circles[j], vertex[i])){
      D seta = arg(vertex[i]-circles[j].fs);
      onC[j].pb( pdi(seta,i) );
      cross[i]++;
    }
  }

  rep(i,circles.sz){
    sort(all(onC[i]));
    rep(j,onC[i].sz){
      int a = onC[i][j].sc, b = onC[i][(j+1)%onC[i].sz].sc;
      if( cross[a]>1 && cross[b]>1 )continue;
      D d = onC[i][(j+1)%onC[i].sz].fs - onC[i][j].fs;
      if(d<0)d += 2*PI;
      res[a].pb( edge(d*100.0,b) );
      res[b].pb( edge(d*100.0,a) );
    }
  }

  vs = lower_bound(all(vertex),start) - vertex.begin();
  vg = lower_bound(all(vertex),goal) - vertex.begin();
  return res;
}

int main(){
  int n,gx,gy;
  cin >> n >> gx >> gy;
  P s(0,0), g(gx,gy);

  vector<C> c(n);
  rep(i,n){
    int x,y;
    cin >> x >> y;
    c[i] = C(P(x,y),100);
  }

  vector<L> segs;
  segs.pb(L(s,g));
  rep(i,n){
    vector<L> tmp = adj_line(c[i],s);
    for(L l : tmp)segs.pb(L(s,cp_cir_to_line(c[i],l)[0]));
    tmp = adj_line(c[i],g);
    for(L l : tmp)segs.pb(L(g,cp_cir_to_line(c[i],l)[0]));
    rep(j,i){
      tmp = common_adj_line(c[i],c[j]);
      for(L l : tmp)segs.pb(L(cp_cir_to_line(c[i],l)[0], cp_cir_to_line(c[j],l)[0]));
    }
  }

  segs = remove_cross(c, segs);

  int a,b;
  vector< vector<edge> > graph = make_graph(c,segs,s,g,a,b);

  vector<D> dis(graph.sz,INF);
  dis[a] = 0;
  priority_queue<pdi, vector<pdi>, greater<pdi> > q;
  q.push(pdi(0,a));

  while(q.size()){
    pdi p = q.top(); q.pop();
    D d = p.fs; int v = p.sc;
    if(dis[v] + EPS < d)continue;
    if(v == b)break;

    for(edge e : graph[v]){
      D nd = d + e.fs;
      int u = e.sc;
      if(dis[u] > nd+EPS){
	dis[u] = nd;
	q.push(pdi(nd,u));
      }
    }
  }

  cout << fixed << setprecision(9) << (EQ(dis[b],INF)?0.0:dis[b]) << endl;
}