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:
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

class range {
    struct Iterator {
        int val, inc;
        int operator*() {return val;}
        bool operator!=(Iterator& rhs) {return val < rhs.val;}
        void operator++() {val += inc;}
    };
    Iterator i, n;
    public:
    range(int e) : i({0, 1}), n({e, 1}) {}
    range(int b, int e) : i({b, 1}), n({e, 1}) {}
    range(int b, int e, int inc) : i({b, inc}), n({e, inc}) {}
    Iterator& begin() {return i;}
    Iterator& end() {return n;}
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}
typedef complex<double> P;
typedef vector<P> L;
P vec(L l) { return l[1] - l[0]; }
const double EPS = 1e-6;

double dot(P a, P b) {
    return real(conj(a) * b); 
}
double cross(P a, P b) {
    return imag(conj(a) * b); 
}

P input() {
    double x, y;
    cin >> x >> y;
    return {x, y};
}

const double Rad = 100.0;
struct C{ P p; double r; };
int sign(double x) { return (x > EPS) - (x < -EPS); }
int comp(double x, double y){ return sign(x - y); }

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;
}


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;
}


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 tan_point(const C& c, double th) {
    return c.p + polar(c.r, th);
}

bool is_on(const C& c, const P& p) {
    return comp(abs(c.p - p), c.r) == 0;
}

const double INF = 1e8;
bool iCS(const C& c, const L& s) {
    if(sign(abs(vec(s))) == 0) return is_on(c, s[0]);
    int t = pCS(c, s).size();
    if(t == 0) return false; // ???????????????
    double d = dSP(s, c.p);
    if(sign(d - c.r) == 0) return false; // ??\??????
    // assert(sign(d - c.r) < 0);
    return true; // ?????????
}

int main(){
    iostream_init();
    int N;
    while(cin >> N) {
        P sp = {0.0, 0.0};
        P gp = input();
        vector<C> cs(N);
        REP(i, N) {
            P cp = input();
            cs[i] = {cp, Rad};
        }

        vector<P> ps;
        ps.push_back(sp);
        ps.push_back(gp);

        REP(i, cs.size()) REP(j, cs.size()) if(i != j) {
            auto ths = common_tangents(cs[i], cs[j]);
            for(double th : ths) {
                P p = tan_point(cs[i], th);
                ps.push_back(p);
            }
        }
        REP(i, cs.size()) {
            auto ths = common_tangents(cs[i], {gp, 0.0});
            for(double th : ths) {
                P p = tan_point(cs[i], th);
                ps.push_back(p);
            }
        }
        REP(i, cs.size()) {
            auto ths = common_tangents(cs[i], {sp, 0.0});
            for(double th : ths) {
                P p = tan_point(cs[i], th);
                ps.push_back(p);
            }
        }

        for(auto it = ps.begin(); it != ps.end(); ) {
            bool ok = true;
            REP(j, cs.size()) {
                if(contains(cs[j], *it) == IN) ok = false;
            }
            if(ok) {
                it++;
            } else {
                it = ps.erase(it);
            }
        }
        // REP(i, ps.size()) cout << i << " " << ps[i] << endl;

        double dist[300][300] = {};
        int move[300][300] = {};
        REP(i, ps.size()) REP(j, ps.size()) {
            if(i == j) { dist[i][j] = 0.0; continue; }
            dist[i][j] = INF;

            REP(k, cs.size()) if(is_on(cs[k], ps[i]) && is_on(cs[k], ps[j])) {
                vector<double> ngs;
                bool contained = false;
                REP(h, cs.size()) if(k != h) {
                    auto v = pCC_th(cs[k], cs[h]);
                    for(double th : v) ngs.push_back(th);

                    if(contains(cs[h], ps[i]) != OUT) contained = true;
                    if(contains(cs[h], ps[j]) != OUT) contained = true;
                }

                // assert(not contained); // ???
                if(contained) continue;

                double th1 = arg(ps[i] - cs[k].p);
                double th2 = arg(ps[j] - cs[k].p);
                if(th1 > th2) swap(th1, th2);
                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) {
                    // assert(move[i][j] == 0);
                    move[i][j] = k;
                    dist[i][j] = min(dist[i][j], (th2 - th1) * cs[k].r);
                }
                if(ok2) {
                    // assert(move[i][j] == 0);
                    dist[i][j] = min(dist[i][j], (2.0 * M_PI - (th2 - th1)) * cs[k].r);
                }
            }

            bool ok = true;
            L segment = {ps[i], ps[j]};
            REP(k, cs.size()) {
                if(iCS(cs[k], segment) || comp(dSP(segment, cs[k].p), cs[k].r) < 0) {
                    ok = false;
                }
            }
            if(ok){
                dist[i][j] = min(dist[i][j], abs(ps[i] - ps[j]));
            }
            // printf("dist[%d][%d] = %f\n", i, j, dist[i][j]);
            // if(i == 0) {
            //     // int t = pCS(cs[0], {ps[i], ps[j]}).size();
            //     // double d = dSP({ps[i], ps[j]}, cs[0].p);
            //     // REP(k, cs.size()) cout << iCS(cs[k], {ps[i], ps[j]}) << " "; cout << endl;
            //     // REP(k, cs.size()) cout << pCS(cs[k], {ps[i], ps[j]}).size() << " "; cout << endl;
            // }
        }

        vector<int> prev(ps.size());
        vector<double> ans(ps.size(), INF);
        ans[0] = 0;
        REP(_, ps.size()) {
            REP(i, ps.size()) REP(j, ps.size()) {
                double nd = ans[i] + dist[i][j];
                if(ans[j] > nd) {
                    ans[j] = nd;
                    prev[j] = i;
                }
            }
        }
        vector<int> list;
        int cur = 1;
        while(cur != 0) {
            list.push_back(cur);
            cur = prev[cur];
        }
        // reverse(list.begin(), list.end());
        // REP(i, list.size()) cout << list[i] << " "; cout << endl;
        // REP(i, list.size()) cout << ps[list[i]] << " "; cout << endl;

        // REP(k, ps.size()) REP(i, ps.size()) REP(j, ps.size())  {
        //     dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        // }

        if(ans[1] >= INF) ans[1] = 0;
        cout << ans[1] << endl;
    }

    return 0;
}

/* vim:set foldmethod=marker: */