// Implement 35 min // Debug1 5 min // Debug2 5 min #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; static const double EPS = 1e-9; static const double PI = acos(-1.0); #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, s, n) for (int i = (s); i < (int)(n); i++) #define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++) #define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++) #define MEMSET(v, h) memset((v), h, sizeof(v)) #include typedef complex Point; typedef vector Polygon; static const double INF = 1e+10; #define CURR(P, i) (P[i]) #define NEXT(P, i) (P[(i + 1) % P.size()]) struct Line : public vector { Line() {;} Line(Point a, Point b) { push_back(a); push_back(b); } }; struct Circle { Point p; double r; Circle() {;} Circle(Point p, double r) : p(p), r(r) {;} }; namespace std { bool operator<(const Point &lhs, const Point &rhs) { return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real(); } } inline double cross(const Point &a, const Point &b) { return imag(conj(a) * b); } inline double dot(const Point &a, const Point &b) { return real(conj(a) * b); } inline int ccw(Point a, Point b, Point c) { b -= a; c -= a; if (cross(b, c) > 0) { return 1; } if (cross(b, c) < 0) { return -1; } //if (dot(b, c) < 0) { return 2; } //if (norm(b) < norm(c)) { return -2; } return 0; } bool intersectSP(const Line &s, const Point &p) { return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; } // usage: // g++ -Wall -Dvisualize hoge.cpp // ./a.out 2> data.js // firefox Visualize.html int zoom = 10; #ifdef visualize void ChangeColor(int r, int g, int b) { fprintf(stderr, "c.strokeStyle = 'rgb(%d, %d, %d)';\n", r, g, b); } void DrawPoint(const Point &p) { fprintf(stderr, "circle(%d, %d, %d)\n", (int)(1000 + zoom*p.real()), 1000-(int)(zoom*p.imag()), 2); } void DrawLine(const Line &l) { fprintf(stderr, "line(%d, %d, %d, %d)\n", (int)(1000 + zoom*l[0].real()), 1000-(int)(zoom*l[0].imag()), (int)(1000 + zoom*l[1].real()), 1000-(int)(zoom*l[1].imag())); } void DrawCircle(const Circle &c) { fprintf(stderr, "circle(%d, %d, %d)\n", (int)(1000 + zoom * c.p.real()), 1000 - (int)(zoom * c.p.imag()), (int)(zoom * c.r)); } #else void DrawPoint(const Point &p) {;} void ChangeColor(int r, int g, int b) {;} void DrawLine(Line l) {;} void DrawPolygon(const Polygon &p) {;} void DrawCircle(Circle c) {;} #endif void DrawPath(vector &path) { double d = 0; REP(i, path.size() - 1) { DrawLine(Line(path[i], path[i + 1])); d += abs(path[i] - path[i + 1]); } } //======================================================================= struct Event { double arg; double dist; int index; Event() {;} Event(double arg, double dist, int index) : arg(arg), dist(dist), index(index) {;} bool operator<(const Event &rhs) const { if (fabs(arg - rhs.arg) > EPS) { return arg > rhs.arg; } return dist > rhs.dist; } }; int n; double upper; Point end; vector kui; vector movable; vector ansMovable; bool Hit(Point from, Point to, Point center, Point p) { if (intersectSP(Line(from, to), p) || intersectSP(Line(to, center), p) || intersectSP(Line(center, from), p)) { return true; } int s[3]; s[0] = ccw(p, from, to); s[1] = ccw(p, to, center); s[2] = ccw(p, center, from); if (s[0] * s[1] * s[2] != 0 && s[0] == s[1] && s[1] == s[2]) { return true; } return false; } bool Calc(double sum, int used, Point from, Point c, double r); bool Move(double sum, int used, Point from, Point to, Point center, double r) { if (r - abs(to - center) < -EPS) { return false; } vector es; REP(i, n) { if ((used >> i) & 1) { continue; } if (center != kui[i] && Hit(from, to, center, kui[i])) { double arg = dot(from - center, kui[i] - center) / abs(from - center) / abs(kui[i] - center); double dist = abs(kui[i] - center); es.push_back(Event(arg, dist, i)); } } sort(es.begin(), es.end()); if (es.empty() || kui[es[0].index] == center) { return Calc(sum, used, to, center, r); } Point ncenter = kui[es[0].index]; double nr = r - abs(ncenter - center); movable.push_back(Circle(ncenter, nr)); bool ret = Move(sum, used, from, to, ncenter, nr); movable.pop_back(); return ret; } vector path; vector ansPath; bool Calc(double sum, int used, Point from, Point c, double r) { path.push_back(from); if (sum > upper) { path.pop_back(); return true; } if (from == end) { ansPath = path; ansMovable = movable; upper = min(upper, sum); path.pop_back(); return true; } if (sum + abs(from - end) - upper > EPS) { path.pop_back(); return false; } if (Move(sum + abs(from - end), used, from, end, c, r)) { path.pop_back(); return true; } REP(i, n) { if ((used >> i) & 1) { continue; } double nsum = sum + abs(kui[i] - from); if (nsum > upper) { continue; } Move(nsum, used | (1 << i), from, kui[i], c, r); } path.pop_back(); return false; } double Solve(int _n, Point s, Point e, vector _kui) { n = _n; end = e; kui = _kui; upper = abs(s) + abs(e); double r = abs(s); if (r - abs(e) < -EPS) { return -1; } ansPath.clear(); path.clear(); ansMovable.clear(); movable.clear(); ansPath.push_back(s); ansPath.push_back(Point(0, 0)); ansPath.push_back(e); movable.push_back(Circle(Point(0, 0), r)); Calc(0.0, 0, s, Point(0, 0), r); return upper; } //=================================================================== int main(int argc, char *argv[]) { if (argc > 1) { zoom = atoi(argv[1]); } int n; double sx, sy, ex, ey; while (scanf("%d %lf %lf %lf %lf", &n, &sx, &sy, &ex, &ey) > 0 && n) { vector kui; Point s(sx, sy); Point e(ex, ey); REP(i, n) { double x, y; scanf("%lf %lf", &x, &y); kui.push_back(Point(x, y)); } double ans = Solve(n, s, e, kui); if (ans == -1) { puts("-1"); } else { printf("%.10f\n", ans); } // Draw Answer ChangeColor(0, 0, 0); DrawLine(Line(Point(-100, 100), Point(100, 100))); DrawLine(Line(Point(-100, 0), Point(100, 0))); DrawLine(Line(Point(-100, -100), Point(100, -100))); DrawLine(Line(Point(100, 100), Point(100, -100))); DrawLine(Line(Point(-100, 100), Point(-100, -100))); DrawLine(Line(Point(0, 100), Point(0, -100))); ChangeColor(255, 0, 0); DrawCircle(Circle(s, 1)); ChangeColor(0, 255, 0); DrawCircle(Circle(e, 1)); ChangeColor(0, 0, 255); REP(i, n) { DrawCircle(Circle(kui[i], 1)); } ChangeColor(0, 255, 255); DrawPath(ansPath); ChangeColor(255, 255, 0); //cout << ansMovable.size() << endl; FORIT(it, ansMovable) { DrawCircle(*it); } } }