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 <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

constexpr double EPS = 1e-9;

struct point {
	double x, y;
	explicit point(double x_ = 0.0, double y_ = 0.0):x(x_), y(y_) {}
	point(const point &p):x(p.x), y(p.y) {}

	point operator+(const point &p) const {
		return point(x + p.x, y + p.y);
	}

	point operator-(const point &p) const {
		return point(x - p.x, y - p.y);
	}

	point operator*(double s) const {
		return point(x * s, y * s);
	}

	point operator*(const point &p) const {
		return point(x * p.x - y * p.y, x * p.y + y * p.x);
	}

	point operator/(double s) const {
		return point(x / s, y / s);
	}

	bool operator<(const point &p) const {
		return x + EPS < p.x || (abs(x - p.x) < EPS && y + EPS < p.y);
	}

	bool operator==(const point &p) const {
		return abs(x - p.x) < EPS && abs(y - p.y) < EPS;
	}
};

point rotate90(const point &p) {
	return point(-p.y, p.x);
}

point rotate(const point &p, double theta) {
	const double s = sin(theta), c = cos(theta);
	return point(c * p.x - s * p.y, s * p.x + c * p.y);
}

double angle(const point &p) {
	return atan2(p.y, p.x);
}

double norm(const point &p) {
	return p.x * p.x + p.y * p.y;
}

double abs(const point &p) {
	return sqrt(norm(p));
}

double dot(const point &a, const point &b) {
	return a.x * b.x + a.y * b.y;
}

double cross(const point &a, const point &b) {
	return a.x * b.y - a.y * b.x;
}

struct line {
	point a, b;
	line(const point &a_, const point &b_):a(a_), b(b_){}
};

struct segment {
	point a, b;
	segment(const point &a_, const point &b_):a(a_), b(b_){}
};

struct circle {
	point c;
	double r;
	circle(const point &c_, const double &r_):c(c_), r(r_){}
};

typedef vector<point> polygon;

int ccw(const point &a, point b, point c) {
	b = b - a;
	c = c - a;
	const double tmp = cross(b, c);
	if(tmp > EPS) return 1; // ccw
	if(tmp < -EPS) return -1; // cw
	if(dot(b, c) < 0) return 2; // c, a, b 順に一直線上
	if(norm(b) < norm(c)) return -2; // a, b, c 順に一直線上
	return 0; //a, c, b 順で一直線上
}

point project(const line &l, const point &p) {
	const point dif = l.b - l.a;
	const double tmp = dot(p - l.a, dif) / norm(dif);
	return l.a + dif * tmp;
}

bool intersect(const line &l, const line &m) {
	return abs(cross(l.b - l.a, m.b - m.a)) > EPS || abs(cross(l.b - l.a, m.b - l.a)) < EPS;
}

bool intersect(const line &l, const segment &s) {
	return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < EPS;
}

bool intersect(const line &l, const point &p) {
	return abs(ccw(l.a, l.b, p)) != 1;
}

bool intersect(const segment &s, const segment &t) {
	return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0
		&& ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

bool intersect(const segment &s, const point &p) {
	return ccw(s.a, s.b, p) == 0;
}

bool intersect(const circle &c, const point &p) {
	return abs(c.c - p) + EPS < c.r;
}

bool intersect(const circle &c, const circle &d) {
	return abs(c.c - d.c) < c.r + d.r + EPS && abs(c.c - d.c) + EPS > abs(c.r - d.r);
}

double dist(const line &l, const point &p) {
	return abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);
}

double dist(const line &l, const line &m) {
	return intersect(l, m) ? 0 : dist(l, m.a);
}

double dist(const line &l, const segment &s) {
	return intersect(l, s) ? 0 : min(dist(l, s.a), dist(l, s.b));
}

double dist(const segment &s, const point &p) {
	if(dot(s.b - s.a, p - s.a) < 0) return abs(p - s.a);
	if(dot(s.a - s.b, p - s.b) < 0) return abs(p - s.b);
	return dist(line(s.a, s.b), p);
}

double dist(const segment &s, const segment &t) {
	if(intersect(s, t)) return 0;
	return min(min(dist(s, t.a), dist(s, t.b)), min(dist(t, s.a), dist(t, s.b)));
}

double dist(const point &a, const point &b) {
	return abs(a - b);
}

bool intersect(const circle &c, const segment &s) {
	return dist(s, c.c) + EPS < c.r;
}

point crosspoint(const line &l, const line &m) {
	const double tmp = cross(l.b - l.a, m.b - m.a);
	if(abs(tmp) < EPS) return l.a; // 平行
	return m.a + (m.b - m.a) * (cross(l.b - l.a, l.a - m.a) / tmp);
}

// 先にintersectで交差判定をすること
point crosspoint(const segment &s, const segment &t) {
	const double tmp = cross(s.b - s.a, t.b - t.a);
	if(abs(tmp) < EPS) { // 一直線上
		if(intersect(s, t.a)) return t.a;
		if(intersect(s, t.b)) return t.b;
		if(intersect(t, s.a)) return s.a;
		return s.b;
	}
	return t.a + (t.b - t.a) * (cross(s.b - s.a, s.b - t.a) / tmp);
}

//先に，intersectを用いて交差判定を行うこと
vector<point> crosspoint(const circle &c, const circle &d) {
	vector<point> res;
	if(abs(c.c - d.c) < EPS) return res; // 中心の座標が同じ

	const double tmp = abs(c.c - d.c);
	const double rc = (tmp * tmp + c.r * c.r - d.r * d.r) / (tmp + tmp);
	const double rs = sqrt(c.r * c.r - rc * rc);
	const point diff = (d.c - c.c) / tmp;
	res.emplace_back(c.c + diff * point(rc, rs));
	res.emplace_back(c.c + diff * point(rc, -rs));
	return res;
}

vector<point> crosspoint(const circle &c, const line &l) {
	vector<point> res;
	const point h = project(l, c.c);
	const double d = abs(h - c.c);
	if(d > c.r + EPS) {
		// nothing
	}
	else if(d > c.r - EPS) {
		res.emplace_back(h);
	}
	else if(d <= c.r - EPS) {
		point v = l.b - l.a;
		v = v * sqrt(c.r * c.r - d * d) / abs(v);
		res.emplace_back(h - v);
		res.emplace_back(h + v);
	}

	return res;
}

vector<point> crosspoint(const circle &c, const segment &s) {
	vector<point> res;
	vector<point> tmp = crosspoint(c, line(s.a, s.b));
	for(const auto &p : tmp) {
		if(intersect(s, p)) res.emplace_back(p);
	}
	return res;
}

double rad(point a, point b, const point &base = point(0, 0)) {
	const int c = ccw(base, a, b);
	if(abs(c) != 1) return 0;
	a = a - base;
	b = b - base;
	return c * acos(dot(a, b) / (abs(a) * abs(b)));
}

double areaTriangle(const point &a, const point &b, const point &c) {
	return abs(cross(a - c, b - c)) / 2.0;
}

double area(const polygon &P) {
	const int n = P.size();
	if(n < 3) return 0;
	if(n == 3) return areaTriangle(P[0], P[1], P[2]);

	double res = 0.0;
	point prev = P.back();

	for(const auto &curr : P) {
		res += cross(prev, curr);
		prev = curr;
	}
	return abs(res) * 0.5;
}

double area(circle c, point a, point b) {
    a = a - c.c;
    b = b - c.c;
    c.c = c.c - c.c;

    const auto cp = crosspoint(c, line(a, b));
    if(cp.size() == 0) return c.r * c.r * rad(a, b) / 2;

    const bool b1 = abs(a) > c.r + EPS;
    const bool b2 = abs(b) > c.r + EPS;

    if(b1 && b2) {
        if(dot(a - cp.front(), b - cp.front()) < EPS && dot(a - cp.back(), b - cp.back()) < EPS) {
            return (c.r * c.r * (rad(a, b) - rad(cp.front(), cp.back()))
                    + cross(cp.front(), cp.back())) / 2;
        }
        else {
            return c.r * c.r * rad(a, b) / 2;
        }
    }
    else if(b1) {
        return (c.r * c.r * rad(a, cp.front()) + cross(cp.front(), b)) / 2;
    }
    else if(b2) {
        return (c.r * c.r * rad(cp.back(), b) + cross(a, cp.back())) / 2;
    }
    else {
        return cross(a, b) / 2;
    }
}

double area(const circle &c, const polygon &P) {
    double res = 0.0;
    point prev = P.back();

    for(const auto &curr : P) {
        res += area(c, prev, curr);
        prev = curr;
    }

    return abs(res);
}

// L.aからL.bの方向を見た場合に，点aが左側に来る．
line bisector(const point &a, const point &b) {
	return line(point((a.x - a.y + b.x + b.y) / 2.0, (a.y + a.x + b.y - b.x) / 2.0),
				point((a.x + a.y + b.x - b.y) / 2.0, (a.y - a.x + b.y + b.x) / 2.0));
}

// 点集合 pointsの凸包を求める．
polygon convex_hull(vector<point> points) {
	const int n = points.size();
	if(n <= 3) return points;

	sort(points.begin(), points.end());
	int k = 0;
	polygon res;
	res.resize(2 * n);
	for(int i = 0; i < n; res[k++] = points[i++]) {
		while(k >= 2 && ccw(res[k - 2], res[k - 1], points[i]) <= 0) --k;
	}

	const int t = k + 1;
	for(int i = n - 2; i >= 0; res[k++] = points[i--]) {
		while(k >= t && ccw(res[k - 2], res[k - 1], points[i]) <= 0) --k;
	}

	res.resize(k - 1);
	return res;
}

// L.aからL.bを向いた時の左側を残して切断する．
polygon convex_cut(const polygon &P, const line &l) {
	polygon res;
	point prev = P.back();
	int pc = ccw(l.a, l.b, prev);

	for(const auto &curr : P) {
		const int cc = ccw(l.a, l.b, curr);

		if(pc != -1) {
			res.emplace_back(prev);
		}
		if(pc * cc < 0) {
			res.emplace_back(crosspoint(l, line(prev, curr)));
		}

		prev = curr;
		pc = cc;
	}

	return res;
}

vector<point> tangent(const circle &c, const point &p) {
	const double x = norm(p - c.c);
	double d = x - c.r * c.r;
	if(d < -EPS) return vector<point>();
	d = max(d, 0.0);
	const point q1 = (p - c.c) * (c.r * c.r / x);
	const point q2 = rotate90((p - c.c) * (-c.r * sqrt(d) / x));
	vector<point> res;
	res.emplace_back(c.c + q1 - q2);
	res.emplace_back(c.c + q1 + q2);
	return res;
}

vector<line> tangent(const circle &a, const circle &b) {
	vector<line> res;
	if(abs(a.r - b.r) < EPS) {
		point dir = b.c - a.c;
		dir = rotate90(dir * (a.r / abs(dir)));
		res.emplace_back(a.c + dir, b.c + dir);
		res.emplace_back(a.c - dir, b.c - dir);
	}
	else {
		point p = a.c * (-b.r) + b.c * a.r;
		p = p * (1.0 / (a.r - b.r));
		vector<point> ps = tangent(a, p), qs = tangent(b, p);
		for(unsigned i = 0; i < min(ps.size(), qs.size()); ++i) {
			res.emplace_back(ps[i], qs[i]);
		}
	}

	point p = a.c * b.r + b.c * a.r;
	p = p * (1.0 / (a.r + b.r));
	vector<point> ps = tangent(a, p), qs = tangent(b, p);
	for(unsigned i = 0; i < min(ps.size(), qs.size()); ++i) {
		res.emplace_back(ps[i], qs[i]);
	}

	return res;
}

// 三角形と点の包含関係，境界は含む．
// 含まない場合は == -1を <= 0とする．
bool contain_triangle(const polygon &triangle, const point &p) {
	const int d1 = ccw(p, triangle[0], triangle[1]);
	const int d2 = ccw(p, triangle[1], triangle[2]);
	const int d3 = ccw(p, triangle[2], triangle[0]);
	return !(d1 * d2 == -1 || d2 * d3 == -1 || d3 * d1 == -1);
}

int sign(double d) {
	return d > EPS ? 1 : d < -EPS ? -1 : 0;
}

// 原点を始点とするベクトルa, b, cについて，
// cが「aからbへ反時計回りで回る角」の内部・辺上・外部のどこにあるか
// + : 内部
// 0 : 辺上 or A = B
// - : 外部
int judge(const point &a, const point &b, const point &c) {
	return sign(cross(a, c)) - sign(cross(b, c)) - sign(cross(a, b));
}

// 多角形と点の包含関係．境界を含む．
bool contain(const polygon &P, const point &p) {
	bool res = false;
	point v1 = P.back() - p;

	for(const auto &curr : P) {
		point v2 = curr - p;

		if(v1.y > v2.y) swap(v1, v2);
		if(v1.y < EPS && EPS < v2.y && cross(v1, v2) > EPS) res = !res;
		if(abs(cross(v1, v2)) < EPS && dot(v1, v2) < EPS) return true;
		// 境界を含まないなら，falseにする．
	}

	return res;
}

// 多角形と線分の包含関係．境界を含む．
bool contain(const polygon &p, const segment &s) {
	const int n = p.size();
	if(!contain(p, s.a + (s.b - s.a) * 0.001)) return false;
	if(!contain(p, s.b + (s.a - s.b) * 0.001)) return false;

	for(int i = 0; i < n; ++i) {
		const auto &prev = p[(i - 1 + n) % n];
		const auto &curr = p[i];
		const auto &next = p[(i + 1) % n];
		if(intersect(s, segment(curr, next))) return false;
		if(intersect(s, curr)) {
			if(judge(prev - curr, next - curr, s.a - curr) > 1) return false;
			if(judge(prev - curr, next - curr, s.b - curr) > 1) return false;
		}
	}

	return true;
}

// 凸多角形と点の包含関係
bool contain_convex(const polygon &c, const point &g, const point &p) {
	const int n = c.size();

	int L = 0, R = n;
	while(L + 1 < R) {
		const int M = (L + R) / 2;
		if(judge(c[L] - g, c[M] - g, p - g) >= 0) {
			R = M;
		}
		else {
			L = M;
		}
	}

	return contain_triangle({g, c[L], c[(L + 1) % n]}, p);
}

istream &operator>>(istream &is, point &p) {
	return is >> p.x >> p.y;
}

ostream &operator<<(ostream &os, const point &p) {
	return os << '(' << p.x << ", " << p.y << ')';
}

int encode(const point &p) {
	static map<point, int> converter;
	if(!converter.count(p)) converter.insert({p, converter.size()});
	return converter[p];
}

struct edge {
	int to;
	double cost;
	edge(int to_, double cost_):to(to_), cost(cost_) {}
};

typedef vector<vector<edge>> graph;

double dijkstra(int s, int g, const graph &G) {
	typedef pair<double, int> P;

	const int n = G.size();

	vector<double> dist(n, INT_MAX);
	priority_queue<P, vector<P>, greater<P>> que;

	dist[s] = 0;
	que.push({0, s});

	while(!que.empty()) {
		const double d = que.top().first;
		const int v = que.top().second;
		que.pop();

		if(dist[v] + EPS < d) continue;
		if(v == g) return d;

		for(const auto &e : G[v]) {
			const double next_dist = d + e.cost;

			if(dist[e.to] > next_dist + EPS) {
				dist[e.to] = next_dist;
				que.push({next_dist, e.to});
			}
		}
	}

	return -1;
}

bool intersect(const circle &c1, const point &p1, const point &p2, const circle &c2) {
	if(intersect(c2, p1) || intersect(c2, p2)) return true;

	double theta = angle(p2 - c1.c) - angle(p1 - c1.c);
	if(theta < 0.0) theta += 2 * M_PI;;

	for(const auto &cp : crosspoint(c1, c2)) {
		double phi = angle(cp - c1.c) - angle(p1 - c1.c);

		if(phi < 0.0) phi += 2 * M_PI;
		if(phi < theta + EPS) return true;
	}

	return false;
}

void add_edge(int v, int u, double d, graph &G) {
	G[v].emplace_back(u, d);
	G[u].emplace_back(v, d);
}

void print_point(const point &p) {
	cerr << "rect(" << p.x << "," << p.y << "," << p.x + 5 << "," << p.y + 5 << ")" << endl;
}

void print_circle(const circle &c) {
	cerr << "circle(" << c.c.x << "," << c.c.y << "," << c.r << ")" << endl;
}

void print_segment(const segment &seg) {
	cerr << "line(" << seg.a.x << "," << seg.a.y << "," << seg.b.x << "," << seg.b.y << ")" << endl;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(10);

	constexpr int radius = 100;

	int n;
	point s(0, 0), g;

	cin >> n >> g;

	vector<circle> poles;
	poles.reserve(n);

	for(int i = 0; i < n; ++i) {
		point c;
		cin >> c;
		poles.emplace_back(move(c), radius);
	}

	vector<point> points{s, g};
	vector<vector<point>> on_circle(n);

	for(int i = 0; i < n; ++i) {
		const circle &c1 = poles[i];

		for(const auto &p : tangent(c1, s)) {
			points.emplace_back(p);
			on_circle[i].emplace_back(p);
		}

		for(const auto &p : tangent(c1, g)) {
			points.emplace_back(p);
			on_circle[i].emplace_back(p);
		}

		for(int j = i + 1; j < n; ++j) {
			const circle &c2 = poles[j];
			for(const auto &l : tangent(c1, c2)) {
				points.emplace_back(l.a);
				points.emplace_back(l.b);

				if((abs(c1.c - l.a) - c1.r) < EPS) {
					on_circle[i].emplace_back(l.a);
				}
				else {
					on_circle[j].emplace_back(l.a);
				}

				if((abs(c1.c - l.b) - c1.r) < EPS) {
					on_circle[i].emplace_back(l.b);
				}
				else {
					on_circle[j].emplace_back(l.b);
				}
			}
		}
	}

	sort(begin(points), end(points));
	points.erase(unique(begin(points), end(points)), end(points));

	const int V = points.size();
	graph G(V);

	for(int i = 0; i < V; ++i) {
		for(int j = i + 1; j < V; ++j) {
			const segment seg(points[i], points[j]);

			bool ok = true;
			for(const auto &c : poles) {
				if(intersect(c, seg)) {
					ok = false;
					break;
				}
			}

			if(ok) {
				add_edge(encode(points[i]), encode(points[j]), abs(points[i] - points[j]), G);
			}
		}
	}

	for(int i = 0; i < n; ++i) {
		for(const auto &p1 : on_circle[i]) {
			for(const auto &p2 : on_circle[i]) {
				if(p1 == p2) continue;

				bool ok = true;

				for(int j = 0; j < n; ++j) {
					if(i == j) continue;
					if(intersect(poles[i], p1, p2, poles[j])) {
						ok = false;
						break;
					}
				}

				if(ok) {
					double theta = angle(p2 - poles[i].c) - angle(p1 - poles[i].c);
					if(theta < 0.0) theta += 2 * M_PI;
					add_edge(encode(p1), encode(p2), radius * theta, G);
				}
			}
		}
	}

	const auto ans = dijkstra(encode(s), encode(g), G);
	if(ans < 0) {
		cout << "0.0" << endl;
	}
	else {
		cout << ans << endl;
	}

	return EXIT_SUCCESS;
}