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 REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;
void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(5);
}
typedef complex<double> P;
P input() {
    double x, y;
    cin >> x >> y;
    return {x, y};
}
struct C{P p; double r; };
typedef vector<P> L;
P vec(L l) { return l[1] - l[0]; }
const double Rad = 100.0;
const double EPS = 1e-6;
int sign(double x) { return (x > EPS) - (x < -EPS); }
int comp(double x, double y){ return sign(x - y); }
double dot(P a, P b) { return real(conj(a) * b); }
double cross(P a, P b) { return imag(conj(a) * b); }

vector<double> common_tangents(const C& c, const C& d) {
    vector<double> res;
    P v = d.p - c.p;
    double l = abs(v);
    double a = arg(v);
    if(sign(l - abs(c.r - d.r)) > 0) {
        double a1 = acos((c.r - d.r) / l);
        res.push_back(a + a1);
        res.push_back(a - a1);
        if(sign(l - (c.r + d.r)) > 0) {
            double a2 = acos((c.r + d.r) / l);
            res.push_back(a + a2);
            res.push_back(a - a2);
        }
    }
    if(sign(l - abs(c.r - d.r)) == 0 || (sign(l - (c.r + d.r)) == 0 && sign(l) != 0)) {
        res.push_back(a);
    }
    return res;
}

P tangent_point(const C& c, double th) {
    return c.p + polar(c.r, th);
}

const double INF = 1e9;
enum { OUT, ON, IN };

int contains(C c, P p) {
    double d = abs(c.p - p);
    if(sign(d - c.r) > 0) return OUT;
    if(sign(d - c.r) == 0) return ON;
    return IN;
}

double dLP(L l, P p) { 
    return abs(cross(vec(l), p - l[0])) / abs(vec(l));
}

double dSP(L s, P p) {
    if(sign(dot(vec(s), p - s[0])) <= 0) return abs(p - s[0]);
    if(sign(dot(-vec(s), p - s[1])) <= 0) return abs(p - s[1]);
    return dLP(s, p);
}

int ccw(P a, P b, P c) {
    c -= a; b -= a;
    if(cross(b, c) > EPS) return 1;
    if(cross(b, c) < -EPS) return -1;
    if(dot(b, c) < 0) return 2;
    if(norm(b) < norm(c)) return -2;
    return 0;
}

bool iSP(L s, P p) { return ccw(s[0], s[1], p) == 0; }

P proj(L l, P p) {
    double t = dot(p - l[0], vec(l)) / norm(vec(l));
    return l[0] + t * vec(l);
}


vector<P> pCL(C c, L l) {
    vector<P> res;
    P center = proj(l, c.p);
    double d = abs(center - c.p);
    double tt = c.r * c.r - d * d;
    if(sign(tt) == 0) tt = 0;
    if(sign(tt) < 0) return res;
    double t = sqrt(tt);
    P vect = vec(l);
    vect /= abs(vect);
    res.push_back(center - vect * t);
    if(t > EPS) {
        res.push_back(center + vect * t);
    }
    return res;
}

vector<P> pCS(C c, L s) {
    vector<P> res;
    vector<P> nres = pCL(c, s);
    for(int i = 0; i < nres.size(); i++) {
        if(iSP(s, nres[i])) res.push_back(nres[i]);
    }
    return res;
}

bool iCS(const C& c, const L& s) {
    int t = pCS(c, s).size();
    if(t == 0) return false; // ???????????????
    double d = dSP(s, c.p);
    if(sign(d - c.r) == 0) return true; // ??\??????
    return true; // ?????????
}

vector<double> pCC_th(C a, C b) {
    vector<double> res;
    double d = abs(b.p - a.p);
    double l1 = abs(a.r - b.r);
    double l2 = a.r + b.r;
    // if(sign(d) == 0 && sign(l1) == 0) assert(false);
    if(sign(d - l1) < 0 || sign(d - l2) > 0) return {};
    double th1 = arg(b.p - a.p);
    if(sign(d - l1) == 0 || sign(d - l2) == 0) {
        return {}; // ok ???
    } else {
        double th2 = acos( (a.r * a.r - b.r * b.r + d * d) / (2.0 * a.r * d) );
        res.push_back(th1 - th2);
        res.push_back(th1 + th2);
    }
    return res;
}


int main(){
    iostream_init();
    int N;
    cin >> N;
    const P sp = {0, 0};
    const P gp = input();
    vector<C> cs(N);
    REP(i, N) {
        cs[i].p = input();
        cs[i].r = Rad;
    }

    vector<P> ps;
    vector<int> id;
    REP(i, N) REP(j, N) {
        auto v = common_tangents(cs[i], cs[j]);
        for(double th : v) {
            P p = tangent_point(cs[i], th);
            ps.push_back(p);
            id.push_back(i);
        }
    }
    REP(i, N) {
        for(P cp : {sp, gp}) {
            auto v = common_tangents(cs[i], {cp, 0.0});
            for(double th : v) {
                P p = tangent_point(cs[i], th);
                ps.push_back(p);
                id.push_back(i);
            }
        }
    }
    ps.push_back(sp);
    ps.push_back(gp);
    id.push_back(-1);
    id.push_back(-2);
    const int ST = ps.size() - 2;
    const int GL = ps.size() - 1;

    double dist[800][800] = {};
    int M = ps.size();
    assert(M < 800);
    REP(i, M) REP(j, M) dist[i][j] = (i == j ? 0.0 : INF);

    REP(i, M) {
        bool contained = false;
        REP(k, cs.size()) {
            if(contains(cs[k], ps[i]) == IN) contained = true;
        }
        if(contained) continue;

        REP(j, M) {
            if(sign(abs(ps[i] - ps[j])) == 0) {
                dist[i][j] = 0;
                continue;
            }

            if(id[i] == id[j]) {
                const C& c = cs[ id[i] ];
                double th1 = arg(ps[i] - c.p);
                double th2 = arg(ps[j] - c.p);
                if(th1 > th2) swap(th1, th2);
                vector<double> ngs;
                REP(k, cs.size()) if(k != id[i]) {
                    auto v = pCC_th(c, cs[k]);
                    for(double th : v) ngs.push_back(th);
                }

                bool ok1 = true;
                for(double th : ngs)
                    if(comp(th1, th) <= 0 && comp(th, th2) <= 0)
                        ok1 = false;

                bool ok2 = true;
                for(double th : ngs)
                    if(comp(th1, th) >= 0 || comp(th, th2) >= 0)
                        ok2 = false;

                if(ok1) {
                    dist[i][j] = min(dist[i][j], (th2 - th1) * c.r);
                }
                if(ok2) {
                    dist[i][j] = min(dist[i][j], (2.0 * M_PI - (th2 - th1)) * c.r);
                }
            }

            bool straight = true;
            REP(k, cs.size()) {
                double d = dSP({ps[i], ps[j]}, cs[k].p);
                if(comp(d, cs[k].r) < 0) straight = false;
            }
            if(straight) dist[i][j] = abs(ps[i] - ps[j]);
        }
    }

    REP(k, M) REP(i, M) REP(j, M) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    if(dist[ST][GL] >= INF) dist[ST][GL] = 0;
    cout << dist[ST][GL] << endl;
    return 0;
}

/* vim:set foldmethod=marker: */