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<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const long double eps = 1e-8, PI = acos(-1);

inline int sign(long double x) {
	return x < -eps ? -1 : x > eps;
}

inline long double sqr(long double x) {
	return x * x;
}

int tx, ty;

struct Point {
	long double x, y;

	Point (long double x = 0, long double y = 0) : x(x), y(y) {}

	void in() {
		scanf("%d%d", &tx, &ty);
		x = tx, y = ty;
	}

	Point operator + (const Point &a) const {
		return Point(x + a.x, y + a.y);
	}

	Point operator - (const Point &a) const {
		return Point(x - a.x, y - a.y);
	}

	Point operator * (const long double &k) const {
		return Point(x * k, y * k);
	}

	Point operator / (const long double &k) const {
		return Point(x / k, y / k);
	}

	Point turn90() const {
		return Point(-y, x);
	}

	long double len() const {
		return sqrt(x * x + y * y);
	}

	long double len2() const {
		return x * x + y * y;
	}

	long double ang() const {
		return atan2(y, x);
	}
};

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

long double det(const Point &a, const Point &b) {
	return a.x * b.y - a.y * b.x;
}

struct Circle {
	Point o;
	long double r;

	bool on(const Point &p) const {
		return sign((p - o).len() - r) == 0;
	}

	bool in(const Point &p) const {
		return sign((p - o).len() - r) < 0;
	}

	long double ang(const Point &p) const {
		return (p - o).ang();
	}

	Point getPoint(const long double ang) const {
		return o + Point(cos(ang), sin(ang)) * r;
	}
};

struct Line {
	Point a, b;

	Line(Point a = Point(0, 0), Point b = Point(0, 0)) : a(a), b(b) {}
};

vector<Point> circleIntersectLine(const Circle &c, const Line &l) {
	long double x = dot(l.a - c.o, l.b - l.a),
		   y = (l.b - l.a).len2(),
		   d = x * x - y * ((l.a - c.o).len2() - c.r * c.r);
	vector<Point> ret;
	if (d < eps) {
		return ret;
	}
	if (d < 0) {
		d = 0;
	}
	Point p = l.a - ((l.b - l.a) * (x / y)), delta = (l.b - l.a) * (sqrt(d) / y);
	ret.push_back(p + delta);
	ret.push_back(p - delta);
	return ret;
}

vector<Point> circleIntersectCircle(const Circle &c1, const Circle &c2) {
	long double x = (c1.o - c2.o).len2(),
		y = ((sqr(c1.r) - sqr(c2.r)) / x + 1) / 2,
		d = sqr(c1.r) / x - sqr(y);
	vector<Point> ret;
	if (d < -eps) {
		return ret;
	}
	if (d < 0) {
		d = 0;
	}
	Point p = c1.o + (c2.o - c1.o) * y, delta = ((c2.o - c1.o) * sqrt(d)).turn90();
	ret.push_back(p - delta);
	ret.push_back(p + delta);
	return ret;
}

vector<Point> circleTangentPoint(const Circle &c, const Point &p0) {
	long double x = (p0 - c.o).len2(),
		d = x - c.r * c.r;
	vector<Point> ret;
	if (d < -eps) {
		return ret;
	}
	if (d < 0) {
		d = 0;
	}
	Point p = (p0 - c.o)* (c.r * c.r / x), delta = ((p0 - c.o) * (-c.r * sqrt(d) / x)).turn90();
	ret.push_back(c.o + p + delta);
	ret.push_back(c.o + p - delta);
	return ret;
}

vector<Line> circleTangentCircle(const Circle &c0, const Circle &c1) {
	vector<Line> ret;
	if (sign(c0.r - c1.r) == 0) {
		Point dir = c1.o - c0.o;
		dir = (dir * (c0.r / dir.len())).turn90();
		ret.push_back(Line(c0.o + dir, c1.o + dir));
		ret.push_back(Line(c0.o - dir, c1.o - dir));
	} else {
		Point p = (c1.o * c0.r - c0.o * c1.r) / (c0.r - c1.r);
		vector<Point> ret1 = circleTangentPoint(c0, p), ret2 = circleTangentPoint(c1, p);
		for (int i = 0; i < (int)ret1.size() && i < (int)ret2.size(); ++i) {
			ret.push_back(Line(ret1[i], ret2[i]));
		}
	}
	Point p = (c0.o * c1.r + c1.o * c0.r) / (c1.r + c0.r);
	vector<Point> ret1 = circleTangentPoint(c0, p), ret2 = circleTangentPoint(c1, p);
	for (int i = 0; i < (int)ret1.size() && i < (int)ret2.size(); ++i) {
		ret.push_back(Line(ret1[i], ret2[i]));
	}
	return ret;
}

vector<Point> circleCutPoint (const Circle &c) {
	vector<Point> ret;
	ret.push_back(c.o + Point(0, c.r));
	ret.push_back(c.o - Point(0, c.r));
	ret.push_back(c.o + Point(c.r, 0));
	ret.push_back(c.o - Point(c.r, 0));
	return ret;
}

const int N = 8, M = 505;

int n;

Circle c[N];

bool legalPoint(const Point &p) {
	for (int i = 0; i < n; ++i) {
		if (c[i].in(p)) {
			return false;
		}
	}
	return true;
}

bool legalArc(const Point &a, const Point &b, const Circle &c) {
	long double a1 = c.ang(a), a2 = c.ang(b), a3;
	if (a1 > a2) {
		swap(a1, a2);	
	}
	if (a2 - a1 < PI) {
		a3 = (a1 + a2) / 2;
	} else {
		a3 = (a1 + a2 + 2 * PI) / 2;
	}
	return legalPoint(c.getPoint(a3));
}

long double getArcLen(const Point &a, const Point &b, const Circle &c) {
	long double d = fabs(c.ang(a) - c.ang(b));
	d = min(d, 2 * PI - d);
	return c.r * d;
}

bool onSeg(const Line &l, const Point &p) {
	return sign(dot(p - l.a, l.b - l.a)) > 0 && sign(dot(p - l.b, l.a - l.b)) > 0;
}

bool legal(const Line &l) {
	for (int i = 0; i < n; ++i) {
		vector<Point> tp = circleIntersectLine(c[i], l);
		if (tp.size() == 0) {
			continue;
		}
		for (int j = 0; j < (int)tp.size(); ++j) {
			if (onSeg(l, tp[j])) {
				return false;
			}
		}
	}
	return legalPoint((l.b + l.a) / 2);
}

long double g[M][M];

int main() {
	scanf("%d", &n);
	Point s = Point(0, 0);
	Point t;
	t.in();
	for (int i = 0; i < n; ++i) {
		c[i].o.in();
		c[i].r = 100;
	}
	vector<Point> key;
	key.push_back(s);
	key.push_back(t);
	for (int i = 0; i < n; ++i) {
		vector<Point> tp = circleTangentPoint(c[i], s);	
		for (int j = 0; j < (int)tp.size(); ++j) {
			key.push_back(tp[j]);
		}
		tp = circleTangentPoint(c[i], t);
		for (int j = 0; j < (int)tp.size(); ++j) {
			key.push_back(tp[j]);
		}
		tp = circleCutPoint(c[i]);
		for (int j = 0; j < (int)tp.size(); ++j) {
			key.push_back(tp[j]);
		}
		for (int j = i + 1; j < n; ++j) {
			vector<Line> tl = circleTangentCircle(c[i], c[j]);
			for (int k = 0; k < (int)tl.size(); ++k) {
				key.push_back(tl[k].a);
				key.push_back(tl[k].b);
			}
			tp = circleIntersectCircle(c[i], c[j]);
			for (int k = 0; k < (int)tp.size(); ++k) {
				key.push_back(tp[k]);
			}
		}
	}
	int m = key.size();
	for (int i = 0; i < m; ++i) {
		g[i][i] = 0;
		Point a = key[i];
		for (int j = i + 1; j < m; ++j) {
			Point b = key[j];
			long double dis = 1e100;
			if (legal(Line(a, b))) {
				dis = (a - b).len();
			}
			g[i][j] = g[j][i] = dis;
		}
	}
	for (int i = 0; i < n; ++i) {
		vector<pair<long double, int> > ps;
		for (int j = 0; j < m; ++j) {
			if (c[i].on(key[j])) {
				ps.push_back(make_pair(c[i].ang(key[j]), j));
			}
		}
		sort(ps.begin(), ps.end());
		for (int j = 0; j < (int)ps.size(); ++j) {
			int u = ps[j].second, v = ps[(j + 1) % ps.size()].second;
			if (legalArc(key[u], key[v], c[i])) {
				long double len = getArcLen(key[u], key[v], c[i]);
				g[u][v] = g[v][u] = min(g[u][v], len);
			}
		}
	}
	/*
	for (int i = 0; i < m; ++i) {
		for (int j = i + 1; j < m; ++j) {
			cout << key[i].x << ' ' << key[i].y << ' ' << key[j].x << ' ' << key[j].y << ' ' << g[i][j] << endl;
		}
	}
	*/
	for (int k = 0; k < m; ++k) {
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < m; ++j) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}
	long double ans = g[0][1];
	if (ans > 1e6) {
		ans = 0;
	}
	printf("%.12f\n", (double)ans);
	return 0;
}