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))
#define getidx(ary,key) lower_bound(_all(arg),key)-begin(arg)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))

using namespace std;

using R=long double;
const R EPS = 1E-11; //[-1000:1000]->EPS=1e-8
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>;

constexpr 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_x(const P& p,const P& q){return sgn(real(p-q))?real(p)<real(q):sgn(imag(p-q));}
inline bool cmp_y(const P& a, const P& b){return sgn(imag(a-b)) ? imag(a-b)<0 : sgn(real(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;}
bool operator <  (const L& a,const L& b){ return a.s==b.s?a.t<b.t:a.s<b.s;}
bool operator == (const L& a,const L& b){ return a.s==b.s&&a.t==b.t;}


//?????? dot ?????? det
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 R dat(P o,P a,P b){a-=o,b-=o; return imag(a*b);}

inline P vec(L l){return l.t-l.s;}

// ?°???± verify AOJ CGL_1_A
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);}
// ????°? verify AOJ CGL_1_B
P refl(L l,P p){ return R(2.0)*proj(l,p)-p;}
// CCW verify AOJ CGL_1_C
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????????????????????????
}

// ?????´ ?????? verify AOJ CGL_2_A
bool vertical(L a, L b) {return sgn(dot(O,vec(a),vec(b)))==0;}
bool parallel(L a, L b) {return sgn(det(O,vec(a),vec(b)))==0;}

// ????????´????????? 
bool eql(L a,L b){ return (parallel(a,b) && sgn(det(a.s,a.t,b.s))==0);}

// ???????????????verify AOJ CGL_2_B ???????????????????????´??????1,????????´??????0
bool ill(L a,L b){ return parallel(a,b)==false;}
bool ils(L l,L s,int end=0){ return sgn(det(l.s,l.t,s.s)*det(l.s,l.t,s.t))<=-end;}
bool iss(L a,L b,int end=0){
	int s1=ccw(a.s,a.t,b.s)|ccw(a.s,a.t,b.t);
	int s2=ccw(b.s,b.t,a.s)|ccw(b.s,b.t,a.t);
	if(end) return (s1&s2)==(LEFT|RIGHT);
	return (s1|s2)&ON || (s1&s2)==(LEFT|RIGHT);
}

// ?????? verify AOJ CGL_2_C
P cross(L a,L b){
	R s1=det(a.s,b.s,b.t);
	R s2=s1+det(a.t,b.t,b.s);
	return a.s+s1/s2*(a.t-a.s);
}
	
// ?????¢ verify AOJ CGL_2_D
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);
}
R dll(L a,L b){return ill(a,b)?0:dlp(a,b.s);}
R dls(L l,L s){return ils(l,s)?0:min(dlp(l,s.s),dlp(l,s.t));}
R dss(L a,L b){return iss(a,b)?0:min({dsp(a,b.s),dsp(a,b.t),dsp(b,a.s),dsp(b,a.t)});}

// ???
// Verify AOJ 1183
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);
	int res=0;
	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;}

//?????¨??´????????????
// Verify AOJ CGL_7_D
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};
}
//2??????????????????
// Verify AOJ CGL_7_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}); 
}

// ????????\???
// Verify AOJ 2001
L tangent(C c,R t){
	P p=c.c+polar(c.r,t);
	P d=polar(c.r,t)*P(0,1);
	return L{p-d,p+d};
}

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

// ????????±?????\???
// Verify AOJ 2001
VL common_tangent(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(tangent(a,d+i));
		res.push_back(tangent(a,d-i));
	}
	// ??±????????\???
	if(r>=ISC){
		res.push_back(tangent(a,d+o));
		res.push_back(tangent(a,d-o));
	}
	//??\????????±???????????\???
	if(r&ONS) res.push_back(tangent(a,d));
	return res;
}

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

// ??? not verify
R toRagian(R degree){ return degree*PI/180.0;}
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 ??????
P rot (P base,P a,R theta){P tar=a-base;return base+polar(abs(tar), arg(tar)+theta );}

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);
	};

	// ?????¨????????? ??\??? 
	rep(i,n){
		rep(j,4) can(circle[i].c+polar(circle[i].r,j*PI/2.0));
		rep(j,m){
			for(auto &l:tangent(circle[i],point[j]))
				can(proj(l,circle[i].c));
		}
	}

	// ?????¨???????????? ??±?????\??? 
	rep(i,n)rep(j,i){
		if(rcc(circle[i],circle[j])==ISC){
			for(auto &p:pcc(circle[i],circle[j])) 
				can(p);
		}
		for(auto &l:common_tangent(circle[i],circle[j])){
			can(proj(l,circle[i].c));
			can(proj(l,circle[j].c));			
		}
	}
	uniq(candiate);
	move(_all(candiate),back_inserter(point));
	
	m=point.size();
	for(auto &c:circle){
		vector<int> idx;
		rep(i,m) if(sgn(abs(c.c-point[i])-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=c.c+polar(c.r,ang(point[cur]-c.c)+angle/2.0);
			bool ok=true;
			rep(j,n){
				// if(c==circle[j]) continue;
				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;
}

/*
void debug(const VC &circle,const VP &point){
	const int offset=250;
	for(auto &c:circle) cerr << "circle(" << offset+real(c.c) << ", " << -(-offset+imag(c.c)) << ", " << c.r << ");" << endl;
	int n=point.size();
	rep(i,n) for(auto &e:graph[i]){
		P a=point[i],b=point[e.to];
		cout << "Edge" << a << " " << b << endl;
		cerr << "line(" << offset+real(a) << ", " << -(-offset+imag(a)) << ", " << offset+real(b) << ", " << -(-offset+imag(b)) << ");" << endl;
	}
	rep(i,n) cout << point[i] << endl;
}
*/

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);
	// debug(circle,point);

	R ans=dist[1];
	if(ans>=INF) ans=0.0;
	
	cout.precision(20);
	cout << fixed << ans << endl;
	return 0;
}