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 sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define phb push_back
#define fr first
#define sc second
using namespace std;

typedef complex< double > Point;
typedef complex< double > Vector;
typedef pair< double, int > PQNode;
const double kR = 100.0;
const double kEps = 1e-8;
const double kPi = acos(-1.0);
const int kSize = 2000;

int N;
double Gx, Gy, Xi[8], Yi[8];

void read();
void solve();

inline bool feq(double x, double y) { return abs(x - y) < kEps; }
inline bool flt(double x, double y) { return x + kEps < y; }
inline double dot(const Vector &u, const Vector &v) { return real(u * conj(v)); }
inline double cross(const Vector &u, const Vector &v) { return imag(u * conj(v)); }

struct PtCmp {
	bool operator () (const Point &a, const Point &b) const {
		if (!feq(real(a), real(b)))
			return flt(real(a), real(b));
		else
			return flt(imag(a), imag(b));
	}
};

double pt_seg_dst(const Point &x, const Point &a, const Point &b) {
	Vector vax = x - a, vbx = x - b, vab = b - a, vba = a - b;
	if (flt(dot(vax, vab), 0.0))
		return abs(vax);
	else if (flt(dot(vbx, vba), 0.0))
		return abs(vbx);
	else
		return abs(cross(vax, vab) / abs(vab));
}

bool check_seg(const Point &a, const Point &b) {
	for (int i = 0; i < N; ++i)
		if (flt(pt_seg_dst(Point(Xi[i], Yi[i]), a, b), kR))
			return false;
	return true;
}

int main() {
	cout.setf(ios::fixed), cout.precision(10);
	while (cin >> N >> Gx >> Gy)
		read(), solve();
	
	return 0;
}

void read() {
	for (int i = 0; i < N; ++i)
		cin >> Xi[i] >> Yi[i];
}

void solve() {
	Point pstart = Point(0.0, 0.0), pend = Point(Gx, Gy);
	map< Point, int, PtCmp > mpt;
	vector< pair< pair< int, int >, double > > vedge;
	vector< Point > vtlp[8];
	auto fi = [&] (const Point &p) -> void {
		if (!mpt.count(p)) mpt.insert({p, sz(mpt)});
	};
	
	mpt[pstart] = 0, mpt[pend] = 1;
	if (check_seg(pstart, pend))
		vedge.phb({{0, 1}, abs(pend - pstart)});
	
	// tangent lines
	for (int i = 0; i < N; ++i) {
		Point oi(Xi[i], Yi[i]), a, b, c, d, m;
		Vector t;
		double tht;
		
		for (int j = i + 1; j < N; ++j) {
			Point oj(Xi[j], Yi[j]);
			
			// outer tangent
			t = (oj - oi) * (kR / abs(oj - oi));
			a = oi + t * polar(1.0, kPi / 2.0), b = oi + t * polar(1.0, -kPi / 2.0);
			t = (oi - oj) * (kR / abs(oi - oj));
			c = oj + t * polar(1.0, -kPi / 2.0), d = oj + t * polar(1.0, kPi / 2.0);
			
			if (check_seg(a, c)) fi(a), fi(c), vtlp[i].phb(a), vtlp[j].phb(c), vedge.phb({{mpt[a], mpt[c]}, abs(a - c)});
			if (check_seg(b, d)) fi(b), fi(d), vtlp[i].phb(b), vtlp[j].phb(d), vedge.phb({{mpt[b], mpt[d]}, abs(b - d)});
			
			// inner tangent
			if (flt(2 * kR, abs(oi - oj))) {
				m = (oi + oj) / 2.0;
				tht = acos(kR / abs(m - oi));
				t = (oj - oi) * (kR / abs(oj - oi));
				a = oi + t * polar(1.0, tht), b = oi + t * polar(1.0, -tht);
				t = (oi - oj) * (kR / abs(oi - oj));
				c = oj + t * polar(1.0, tht), d = oj + t * polar(1.0, -tht);
				
				if (check_seg(a, c)) fi(a), fi(c), vtlp[i].phb(a), vtlp[j].phb(c), vedge.phb({{mpt[a], mpt[c]}, abs(a - c)});
				if (check_seg(b, d)) fi(b), fi(d), vtlp[i].phb(b), vtlp[j].phb(d), vedge.phb({{mpt[b], mpt[d]}, abs(b - d)});
			}
		}
		
		// start point
		tht = acos(kR / abs(pstart - oi));
		t = (pstart - oi) * (kR / abs(pstart - oi));
		a = oi + t * polar(1.0, tht), b = oi + t * polar(1.0, -tht);
		
		if (check_seg(pstart, a)) fi(a), vtlp[i].phb(a), vedge.phb({{0, mpt[a]}, abs(pstart - a)});
		if (check_seg(pstart, b)) fi(b), vtlp[i].phb(b), vedge.phb({{0, mpt[b]}, abs(pstart - b)});
		
		// end point
		tht = acos(kR / abs(pend - oi));
		t = (pend - oi) * (kR / abs(pend - oi));
		a = oi + t * polar(1.0, tht), b = oi + t * polar(1.0, -tht);
		
		if (check_seg(pend, a)) fi(a), vtlp[i].phb(a), vedge.phb({{1, mpt[a]}, abs(pend - a)});
		if (check_seg(pend, b)) fi(b), vtlp[i].phb(b), vedge.phb({{1, mpt[b]}, abs(pend - b)});
	}
	
	// arcs
	for (int i = 0; i < N; ++i) {
		Point oi(Xi[i], Yi[i]), oz = oi + polar(kR);
		map< Point, int, PtCmp > mang;
		vector< pair< Point, int > > vang;
		
		fi(oz);
		mang[oz] = 0;
		sort(all(vtlp[i]), PtCmp());
		vtlp[i].erase(unique(all(vtlp[i])), vtlp[i].end());
		for (auto &it: vtlp[i])
			mang[it] = 0;

#define _arg(x) (flt(arg(x), 0.0) ? arg(x) + 2 * kPi : arg(x))
		for (int j = 0; j < N; ++j)
			if (j != i) {
				Point oj(Xi[j], Yi[j]), a, b;
				if (flt(abs(oi - oj), 2 * kR)) {
					double tht = acos((abs(oi - oj) / 2) / kR);
					Vector t = (oj - oi) * (kR / abs(oj - oi));
					a = oi + t * polar(1.0, -tht), b = oi + t * polar(1.0, tht);
					fi(a), fi(b);
					
					if (flt(_arg(a - oi), _arg(b - oi)))
						++mang[a], --mang[b];
					else
						++mang[oz], --mang[b], ++mang[a];
				}
			}
		
		for (auto &it: mang)
			vang.phb({it.fr, it.sc});
		
		sort(all(vang), [&] (const pair< Point, int > &a, const pair< Point, int > &b) -> bool {
			return flt(_arg(a.fr - oi), _arg(b.fr - oi));
		});
		
		int c = 0;
		for (int k = 0; k < sz(vang) - 1; ++k)
			if ((c += vang[k].sc) == 0)
				vedge.phb({{mpt[vang[k].fr], mpt[vang[k + 1].fr]}, (_arg(vang[k + 1].fr - oi) - _arg(vang[k].fr - oi)) * kR});
		if (c == 0)
			vedge.phb({{mpt[vang[0].fr], mpt[vang.back().fr]}, (2 * kPi - _arg(vang.back().fr - oi)) * kR});
	}
#undef _arg
	
	// build graph
	vector< pair< int, double > > gph[kSize];
	for (auto &it: vedge) {
		gph[it.fr.fr].phb({it.fr.sc, it.sc});
		gph[it.fr.sc].phb({it.fr.fr, it.sc});
	}
	
	priority_queue< PQNode, vector< PQNode >, greater< PQNode > > pq;
	double f[kSize];
	
	fill(&f[0], &f[kSize], 1e10);
	f[0] = 0.0, pq.push({0.0, 0});
	while (!pq.empty()) {
		PQNode tp(pq.top()); pq.pop();
		int u = tp.sc, v;
		double cst = tp.fr, eln;
		
		if (u == 1)
			break;
		
		if (flt(f[u], cst))
			continue;
		
		for (auto &it: gph[u])
			if (flt(f[u] + (eln = it.sc), f[v = it.fr]))
				f[v] = f[u] + eln, pq.push({f[v], v});
	}
	
	cout << (flt(f[1], 1e10) ? f[1] : 0.0) << "\n";
}