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 <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <complex>
#include <iomanip>
#include <queue>
#include <map>
#include <tuple>
using namespace std;

typedef double D;
typedef complex<D> P;
typedef const P &rP;
typedef pair<P,P> seg;
typedef pair<D,int> pdi;
typedef pair<int,int> pii;

const D INF = 1e100;
const D EPS = 1e-8;
const D pi = acos(D(-1.0));

namespace std{
	bool operator< (rP a, rP b){
		if(abs(real(a) - real(b)) > EPS){
			return real(a) < real(b);
		}
		if(abs(imag(a) - imag(b)) > EPS){
			return imag(a) < imag(b);
		}
		return false;
	}
}

D dot(rP a, rP b){
	return real(a) * real(b) + imag(a) * imag(b);
}
D cross(rP a, rP b){
	return real(a) * imag(b) - imag(a) * real(b);
}

vector<P> cs;
vector<D> rs;
vector<vector<pdi> > vs;
map<P,int> mp;

inline int getid(rP p){
	return mp.insert(make_pair(p, mp.size())).first->second;
}
inline D getangle(int idx, rP p){
	return rs[idx] < EPS ? 0.0 : arg(p - cs[idx]);
}
inline void reg(int idx, rP p){
	vs[idx].emplace_back(getangle(idx, p), getid(p));
}

vector<P> intrcc(int a, int b){
	vector<P> ret;
	D r1 = rs[a], r2 = rs[b];
	rP p1 = cs[a], p2 = cs[b];
	D d = abs(p2 - p1);
	if(r1 < EPS || r2 < EPS || d < EPS){ return ret; }
	D phi = arg(p2 - p1);
	D ct = (d * d + r1 * r1 - r2 * r2) / (2.0 * d * r1);
	if(abs(ct) > 1.0 + EPS){ return ret; }
	if(ct < -1.0){ ct = -1.0; }
	else if(ct > 1.0){ ct = 1.0; }
	D t = acos(ct);
	ret.push_back(p1 + polar(r1, phi + t));
	ret.push_back(p1 + polar(r1, phi - t));
	return ret;
}

D distsp(rP a, rP b, rP c){
	if(dot(b - a, c - a) <= 0.0){ return abs(c - a); }
	if(dot(a - b, c - b) <= 0.0){ return abs(c - b); }
	return abs(cross(b - a, c - a)) / abs(b - a);
}

vector<seg> comtang(int idx1, int idx2){
	vector<seg> ret;
	rP p1 = cs[idx1], p2 = cs[idx2];
	D r1 = rs[idx1], r2 = rs[idx2];
	D d = abs(p2 - p1);
	if(d < EPS){ return ret; }
	D a = arg(p2 - p1);
	D b = (r1 - r2) / d;
	if(abs(b) > 1.0){ return ret; }
	D c = asin(b) - 0.5 * pi;
	ret.emplace_back(p1 + polar(r1, a - c), p2 + polar(r2, a - c));
	ret.emplace_back(p1 + polar(r1, a + c), p2 + polar(r2, a + c));
	b = (r1 + r2) / d;
	if(abs(b) > 1.0){ return ret; }
	c = asin(b) - 0.5 * pi;
	ret.emplace_back(p1 + polar(r1, a - c), p2 - polar(r2, a - c));
	ret.emplace_back(p1 + polar(r1, a + c), p2 - polar(r2, a + c));
	return ret;
}

bool check1(const seg &s){
	for(size_t i = 0; i < cs.size(); ++i){
		if(distsp(s.first, s.second, cs[i]) + EPS < rs[i]){
			return false;
		}
	}
	return true;
}

bool check2(rP p){
	for(size_t i = 0; i < cs.size(); ++i){
		if(abs(p - cs[i]) + EPS < rs[i]){
			return false;
		}
	}
	return true;
}

int main(){
	int n;
	D x, y;
	cin >> n >> x >> y;
	cs.resize(n + 2);
	rs.assign(n + 2, 100.0);
	cs[0] = P();
	cs[1] = P(x, y);
	rs[0] = rs[1] = 0.0;
	for(int i = 0; i < n; ++i){
		cin >> x >> y;
		cs[i + 2] = P(x, y);
	}

	vs.resize(n + 2);
	reg(0, cs[0]);
	reg(1, cs[1]);

	vector<tuple<int,int,D> > es;
	for(int i = 0; i < n + 2; ++i){
		for(int j = 0; j < i; ++j){
			vector<P> intr = intrcc(i, j);
			for(rP p : intr){
				reg(i, p);
				reg(j, p);
			}

			vector<seg> ct = comtang(i, j);
			for(const seg & s : ct){
				if(check1(s)){
					reg(i, s.first);
					reg(j, s.second);
					es.emplace_back(
						getid(s.first), getid(s.second), abs(s.first - s.second)
					);
				}
			}
		}
	}
	for(int i = 0; i < n + 2; ++i){
		if(vs[i].empty()){ continue; }
		sort(vs[i].begin(), vs[i].end());
		vs[i].emplace_back(vs[i][0].first + 2.0 * pi, vs[i][0].second);
		vs[i].erase(unique(vs[i].begin(), vs[i].end(), 
			[](const pdi &a, const pdi &b){ return a.second == b.second; }
			), vs[i].end()
		);

		for(size_t j = 1; j < vs[i].size(); ++j){
			D a1 = vs[i][j - 1].first, a2 = vs[i][j].first;
			P p = cs[i] + polar(rs[i], (a1 + a2) * 0.5);
			if(check2(p)){
				es.emplace_back(
					vs[i][j - 1].second, vs[i][j].second, (a2 - a1) * rs[i]
				);
			}
		}
	}

	vector<vector<pdi> > G(mp.size());
	for(const auto &e : es){
		G[get<0>(e)].emplace_back(get<2>(e), get<1>(e));
		G[get<1>(e)].emplace_back(get<2>(e), get<0>(e));
	}

	vector<D> ds(mp.size(), INF);
	ds[vs[0][0].second] = 0.0;
	priority_queue<pdi> pq;
	pq.emplace(0.0, vs[0][0].second);
	while(!pq.empty()){
		D d = -pq.top().first;
		int u = pq.top().second;
		pq.pop();
		if(ds[u] != d){ continue; }
		for(const auto &e : G[u]){
			D nd = d + e.first;
			if(ds[e.second] > nd){
				ds[e.second] = nd;
				pq.emplace(-nd, e.second);
			}
		}
	}
	D ans = ds[vs[1][0].second];
	if(ans == INF){ ans = 0.0; }
	cout << fixed << setprecision(9) << ans << '\n';
}