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 _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))

using namespace std;

using R=long double;
const R EPS = 1E-11;
const R INF = 1E40;
const R PI = acos(R(-1));
inline int sgn(const R& r){ return (r > EPS) - (r < -EPS);}
inline R sq(R x){return sqrt(max<R>(x,0.0));}

using P=complex<R>;
using VP=vector<P>;
using L=struct{P s,t;};
using VL=vector<L>;

const P O = P(0,0);
istream& operator >> (istream& is,P& p){ R x,y;is >> x >> y; p=P(x,y); return is;}
ostream& operator << (ostream& os,P& p){ os << real(p) << " " << imag(p); return os;}

namespace std{
	bool operator <  (const P& a,const P& b){ return sgn(real(a-b))?real(a-b)<0:sgn(imag(a-b))<0;}
	bool operator == (const P& a,const P& b){ return sgn(real(a-b))==0 && sgn(imag(a-b))==0;}
}

inline bool cmp_a(const P& a, const P& b){return sgn(arg(a)-arg(b)) ? arg(a)-arg(b)<0 : sgn(norm(a)-norm(b))<0;}

inline R dot(P o,P a,P b){a-=o,b-=o; return real(conj(a)*b);}
inline R det(P o,P a,P b){a-=o,b-=o; return imag(conj(a)*b);}
inline P vec(L l){return l.t-l.s;}

P proj(P o,P a,P b){ a-=o,b-=o; return a*real(b/a);}
P proj(L l,P p){ return l.s+proj(l.s,l.t,p);}

enum CCW{ LEFT = 1,RIGHT = 2,BACK = 4,FRONT = 8,ON = 16};
inline int ccw(P o,P a, P b) {//???a??¨???b???????????????????????????
	if (sgn(det(o,a,b)) > 0) return LEFT;    // counter clockwise
	if (sgn(det(o,a,b)) < 0) return RIGHT;   // clockwise
	if (sgn(dot(o,a,b)) < 0) return BACK;    // b--base--a on line
	if (sgn(norm(a-o)-norm(b-o)) < 0) return FRONT;   // base--a--b on line
	return ON;// base--b--a on line  a??¨b????????????????????????
}

R dlp(L l,P p){return abs(det(l.s,l.t,p))/abs(vec(l));}
R dsp(L s,P p){
	if(sgn(dot(s.s,s.t,p))<=0) return abs(p-s.s);
	if(sgn(dot(s.t,s.s,p))<=0) return abs(p-s.t);
	return dlp(s,p);
}

using C=struct{P c;R r;};
using VC=vector<C>;
bool operator <  (const C& a,const C& b){ return a.c==b.c?sgn(a.r-b.r)<0:a.c<b.c;}
bool operator == (const C& a,const C& b){ return a.c==b.c&&sgn(a.r-b.r)==0;}

enum RCC{IN=1,ON_IN=2,ISC=4,ON_OUT=8,OUT=16,ONS=10};
int rcc(C a,C b){
	R d=abs(a.c-b.c);
	if(a.r+b.r< d) return OUT;
	if(a.r+b.r==d) return ON_OUT;
	if(abs(a.r-b.r)<d) return ISC;
	if(abs(a.r-b.r)==d) return ON_IN;
	return IN;
}

bool icp(C c,P p,int end=0){return sgn(norm(p-c.c)-norm(c.r))<=-end;}
bool ics(C c,L l,int end=0){return sgn(dsp(l,c.c)-c.r)<=-end;}
bool icsc(C c,L l,int end=0){return ics(c,l) && sgn(max(norm(l.s-c.c),norm(l.t-c.c))-norm(c.r))<=0;}

P cir(C c,R t){return c.c+polar(c.r,t);}

VP pcl(C c, L l) {
	P h=proj(l,c.c);
	P e=(l.t-l.s)/abs(l.t-l.s)*sq(norm(c.r)-norm(h-c.c));
	return VP{h-e,h+e};
}

VP pcc(C a,C b){
	P d=b.c-a.c;
	P w=(norm(d)+norm(a.r)-norm(b.r))/(2.0*norm(d))*d;
	P e=w*P(0,1);
	return pcl(a,{a.c+w-e,a.c+w+e}); 
}

L tan(C c,R t){
	P p=cir(c,t);
	P d=polar(c.r,t)*P(0,1);
	return L{p-d,p+d};
}

VL tan(C c,P p){
	VL res;
	R d=arg(p-c.c),t=acos(c.r/abs(p-c.c));
	res.push_back(tan(c,d+t));
	if(sgn(t)) res.push_back(tan(c,d-t));			
	return res;
}

VL tan(C a,C b){
	VL res;
	R d=arg(b.c-a.c),i=acos((a.r+b.r)/abs(b.c-a.c)),o=acos((a.r-b.r)/abs(b.c-a.c));
	int r=rcc(a,b);
	if(r==OUT){
		res.push_back(tan(a,d+i));
		res.push_back(tan(a,d-i));
	}
	if(r>=ISC){
		res.push_back(tan(a,d+o));
		res.push_back(tan(a,d-o));
	}
	if(r&ONS) res.push_back(tan(a,d));
	return res;
}

const int vmax=5010;
struct node{int to;R cost;};
vector<node> graph[vmax];

R ang (P p){return arg(p);}
R ang (P base,P a,P b) {R res=arg((b-base)/(a-base));return res<0?res+2*PI:res;} // base ??????

inline void add_edge(int f,int t,R c){
	graph[f].push_back({t,c});
	graph[t].push_back({f,c});
}

void circle_arrangement(const VC &circle,VP &point){
	int n=circle.size(),m=point.size();
	VP candiate;
	
	auto can=[&](P p){
		bool ok=true;
		rep(i,n) if(icp(circle[i],p,1)) return;
		candiate.push_back(p);
	};

	// ?????¨????????? ??\??? 
	for(auto &c:circle){
		rep(j,4) can(cir(c,j*PI/2.0));
		rep(j,m) for(auto &l:tan(c,point[j])) can(proj(l,c.c));
	}

	// ?????¨???????????? ??±?????\??? 
	for(auto &c1:circle)for(auto &c2:circle){
		if(rcc(c1,c2)==ISC) for(auto &p:pcc(c1,c2)) can(p);
		for(auto &l:tan(c1,c2)) can(proj(l,c1.c)),can(proj(l,c2.c));			
	}

	uniq(candiate),move(_all(candiate),back_inserter(point)),m=point.size();

	for(auto &c:circle){
		vector<int> idx;
		rep(i,m) if(sgn(norm(c.c-point[i])-norm(c.r))==0) idx.push_back(i);
		int all=idx.size();
		rrep(j,all)rep(i,j)if(!cmp_a(point[idx[i]]-c.c,point[idx[j]]-c.c)) swap(idx[i],idx[j]);
		rep(i,all){
			int cur=idx[i],nxt=idx[(i+1)%all];
			R angle=ang(c.c,point[cur],point[nxt]);
			P mid=cir(c,ang(point[cur]-c.c)+angle/2.0);
			bool ok=true;
			rep(j,n) if(icp(circle[j],mid,1)) ok=false;
			if(ok) add_edge(cur,nxt,c.r*angle);
		}
	}

	rep(i,m)rep(j,i){
		L l={point[i],point[j]};
		bool ok=true;
		for(auto &c:circle) if(ics(c,l,1)) ok=false;
		if(ok) add_edge(i,j,abs(l.t-l.s));
	}
	return;
}

using state=tuple<R,int>;
R dist[vmax];

void dijkstra(int s){
	rep(i,vmax) dist[i]=INF;
	dist[s]=0;
	priority_queue<state,vector<state>,greater<state>> q;
	q.push(state(0.0,s));
	while(!q.empty()){
		R c;int v;
		tie(c,v)=q.top();q.pop();
		for(auto &e:graph[v]){
			R nc=c+e.cost; int nv=e.to;
			if(dist[nv]>nc){
				dist[nv]=nc;
				q.push(state(nc,nv));
			}
		}
	}
	return;
}

int main(void){
	int n;
	P s=O,g;
	cin >> n >> g;
	
	VC circle;
	rep(i,n){
		P c;
		cin >> c;
		circle.push_back({c,100.0});
	}
	VP point={s,g};
	
	circle_arrangement(circle,point);
	dijkstra(0);
	
	R ans=dist[1];
	if(ans>=INF) ans=0.0;
	
	cout.precision(20);
	cout << fixed << ans << endl;
	return 0;
}