Submission #397796


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long double Real;
typedef complex<Real> Point;
typedef pair<Point, Point> Line;
typedef pair<Point, Real> Circle;
typedef vector<Point> Poly;

const Real eps = 1e-9;

inline bool near(const Point& p, const Point& q){return abs(p - q) < eps;}

inline Real dot(const Point& p, const Point& q){return p.real() * q.real() + p.imag() * q.imag();}
inline Real cross(const Point& p, const Point& q){return p.real() * q.imag() - p.imag() * q.real();}

inline Real angle (const Point& p, const Point& q, const Point& r = 0) {
    return arg((p - r) / (q - r));
}

// ccw_b : old version of ccw.
inline Real ccw_b(const Point& p, const Point& q, const Point& r) {return cross(q - p, r - p);}

/* ccw :
   CD  : counter direction
   CW  : clock wise
   OS  : on segment
   CCW : counter clock wise
   D   : direction
*/
enum LPposit { P_CD = -2, P_CW = -1, P_OS = 0, P_CCW = 1, P_D = 2};
LPposit ccw(const Point& p, const Point& q, const Point& r) {
    Real c = ccw_b(p, q, r);
    if (c < -eps) return P_CW;
    if (c >  eps) return P_CCW;
    if (dot(q - p, r - p) < -eps) return P_CD;
    if (dot(p - q, r - q) < -eps) return P_D;
    return P_OS;
}

inline Real Sabs(const Line& l) {return abs(l.first - l.second); }

inline Real LPdist(const Line& l, const Point& p) {return abs(ccw_b(l.first, l.second, p)) / Sabs(l); }
inline Real SPdist(Line l, Point p) {
    Real a = abs(l.first  - p);
    Real b = abs(l.second - p);
    Real c = Sabs(l);
    if (b * b + c * c > a * a && a * a + c * c > b * b){
        return LPdist(l, p);
    }
    return min(a, b);
}

vector<Point> tangents(const Circle& c, const Point& p) {
    const Point center = c.first;
    const Real radius = c.second;
    const Real dist = abs(center - p);
    const Point q = center + (p - center) / abs(p - center) * radius;
    if (near(dist, radius)) {
        return {q};
    } else if (dist < radius) {
        return {};
    } else {
        const Real deg = M_PI / 2. - asin(radius / dist);
        const Point v = q - center;
        return {center + v * polar((Real)1, deg), center + v * polar((Real)1, -deg)};
    }
}

vector<Line> common_tangents (const Circle& p, const Circle& q) {
    Real pr = p.second, qr = q.second;
    Point pc = p.first, qc = q.first;
    Real d = abs(pc - qc), dr = abs(pr - qr), sr = abs(pr + qr);

    vector<Line> ret;
    if (d > sr) {
        // cross pair
        Point cp = (pc * qr + qc * pr) / sr;
        vector<Point> pts = tangents(p, cp), qts = tangents(q, cp);
        ret.push_back(Line(pts[0], qts[0]));
        ret.push_back(Line(pts[1], qts[1]));
    } else if (abs(d - sr) < eps) {
        // cross pair coinside
        Point cp = (pc * qr + qc * pr) / sr;
        ret.push_back(Line(cp, cp));
    } 

    if (d > dr) {
        // outer pair
        if (abs(pr - qr) < eps) {
            Point v = (qc - pc) / d;
            v *= Point(0, 1);
            ret.push_back(Line(pc + v, qc + v));
            ret.push_back(Line(pc - v, qc - v));
        } else {
            Point cp = pc + (qc - pc) * pr / (pr - qr);
            vector<Point> pts = tangents(p, cp), qts = tangents(q, cp);
            ret.push_back(Line(pts[0], qts[0]));
            ret.push_back(Line(pts[1], qts[1]));
        }
    } else if (abs(d - dr) < eps) {
        // outer pair coinside
        Point cp = (qc - pc) * pr / (pr - qr);
        ret.push_back(Line(cp, cp));
    } 

    return ret;
}

struct ShortestPath {
    struct edge { int to; Real cost; };
    static const Real inf;
    int v;
    vector<vector<edge> > g;
    ShortestPath(int _v): v(_v), g(v) {}
    void add_edge (int from, int to, Real cost) {
        g[from].push_back((edge){to, cost});
        g[to].push_back((edge){from, cost});
    }
    vector<Real> shortest_path(int init) {
        vector<Real> min_cost(v, inf);
        priority_queue<pair<Real, int> > q;
        min_cost[init] = 0;
        q.push(make_pair(0, init));
        while (not q.empty()) {
            Real cost = -q.top().first;
            int pos = q.top().second;
            q.pop();
            
            for (int i = 0; i < g[pos].size(); ++i) {
                int npos = g[pos][i].to;
                Real ncost = cost + g[pos][i].cost;
                if (ncost < min_cost[npos]) {
                    min_cost[npos] = ncost;
                    q.push(make_pair(-ncost, npos));
                }
            }
        }
        return min_cost;
    }

    Real shortest_path(int s, int t) {
        return shortest_path(s)[t];
    }
};
const Real ShortestPath::inf = 1e300;

namespace std{
    bool operator<(const Point& a, const Point& b) {
        return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
    }
}

// === end lib ===
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)

struct witch {
    Point pos;
    Real r_init, r_v;
    witch (Point p, Real ri, Real rv): pos(p), r_init(ri), r_v(rv) {}
    Circle get_circle (Real time) {
        return Circle(pos, r_init + r_v * time);
    }
};

Point start, goal;
Real v;
int n;
vector<witch> witches;

Point parse_point () {
    Real x, y;
    cin >> x >> y;
    return Point(x, y);
}

bool test_edge (Point& p, Point& q) {
    for (auto w = witches.begin(); w != witches.end(); ++w) {
        if (SPdist(Line(p, q), w->pos) + eps < w->r_init) {
            return false;
        }
    }
    return true;
}

struct Graph {
    vector<Point> nodes;
    map<Point, int> index;
    vector<tuple<int, int, Real> > edges;
    
    int add_node (Point p) {
        if (index.find(p) == index.end()) {
            const int newid = index.size();
            index[p] = newid;
            nodes.push_back(p);
        }
        return index[p];
    }

    void add_edge (Point p, Point q) {
        if (not test_edge(p, q)) return;
        int pi = add_node(p);
        int qi = add_node(q);
        edges.push_back(make_tuple(pi, qi, abs(p - q)));
    }

    void add_arc (Point p, Point q, Real cost) {
        int pi = add_node(p);
        int qi = add_node(q);
        edges.push_back(make_tuple(pi, qi, cost));
    }

    Real shortest_path (Point fr, Point to) {
        ShortestPath sp(index.size());
        rep(i, edges.size()) {
            int efr = get<0>(edges[i]);
            int eto = get<1>(edges[i]);
            Real cost = get<2>(edges[i]);
            sp.add_edge(efr, eto, cost);
        }
        int fri = add_node(fr);
        int toi = add_node(to);
        return sp.shortest_path(fri, toi);
    }
};

int solve_boss () {
    // redef variables.
    const Point w_pos = witches[0].pos - start;
    const Real r_init = witches[0].r_init, r_v = witches[0].r_v;
    goal -= start;
    start -= start;
    
    // try direct attack
    // for all t in [0, goaltime], at^2 + bt + c >= 0
    const Real goaltime = abs(goal) / v;
    const Real a = pow(v, 2) - pow(r_v, 2);
    const Real b = -2 * (v * dot(goal, w_pos) / abs(goal) + r_init * r_v);
    const Real c = norm(w_pos) - pow(r_init, 2);
    
    const Real axis = -b / (2 * a);
    Real minimum_distance = min(c, a * pow(goaltime, 2) + b * goaltime + c);
    if (0 <= axis && axis <= goaltime) {
        minimum_distance = min(minimum_distance, a * pow(axis, 2) + b * axis + c);
    }
    if (minimum_distance >= 0) {
        cout << goaltime << endl;
        return 0;
    }
    
    // try log spiral
    // decide the direction to meet the curse using binary search
    Real min_angle = 0, max_angle = M_PI;
    rep(_, 200) {
        const Real ang = (min_angle + max_angle) / 2.;
        const Point direction = polar((Real)1, ang + arg(w_pos));
        const Real b2 = -2 * (v * dot(direction, w_pos) / abs(direction) + r_init * r_v);
        const Real D = pow(b2, 2) - 4 * a * c;
        if (D > 0) {
            min_angle = ang;
        } else {
            max_angle = ang;
        }   
    }

    vector<Real> candidate_answer;
    const Real ang = (min_angle + max_angle) / 2.;
    const vector<Point> dirs = {polar((Real)1, arg(w_pos) + ang), polar((Real)1, arg(w_pos) - ang)};
    for (auto dir = dirs.begin(); dir != dirs.end(); ++dir) {
        // binary search to decide when to leave the curse.
        const Real b2 = -2 * (v * dot(*dir, w_pos) / abs(*dir) + r_init * r_v);
        const Real meet_time = -b2 / (2 * a);
        const Point meet_point = start + (*dir) * v * meet_time;
        const Real meet_angle = arg(meet_point - w_pos);
        const LPposit cw = ccw(w_pos, meet_point, meet_point + *dir);
        Real min_runtime = 0, max_runtime = (abs(goal - w_pos) - r_init) / r_v - meet_time;
        if (max_runtime < 0) {
            cout << "Impossible" << endl;
            return 0;
        }
        Real goal_time = 1e100;
        rep(_, 200) {
            const Real runtime = (min_runtime + max_runtime) / 2.;
            const Real leave_time = meet_time + runtime;
            const Real run_angle = (sqrt(pow(v, 2) - pow(r_v, 2)) / r_v) * (log(r_init + r_v * leave_time) - log(r_init + r_v * meet_time));
            if (run_angle > M_PI) {
                max_runtime = runtime;
                continue;
            }
            const Real leave_angle = meet_angle + cw * run_angle;
            const Point outer_vector = polar((Real)1, leave_angle);
            const Point leave_point = w_pos + outer_vector * (r_init + r_v * leave_time);
            const Point run_vector = outer_vector * r_v + cw * sqrt(pow(v, 2.) - pow(r_v, 2.)) * outer_vector * Point(0, 1);

            if (ccw(leave_point, leave_point + run_vector, goal) == cw) {
                min_runtime = runtime;
            } else {
                if (abs(arg(outer_vector / run_vector)) <= acos(r_v / v)) {
                    goal_time = min(goal_time, leave_time + abs(leave_point - goal) / v);
                }
                max_runtime = runtime;
            }
        }
        if (goal_time < (abs(goal - w_pos) - r_init) / r_v) {
            candidate_answer.push_back(goal_time);
        }
    }

    if (candidate_answer.empty()) {
        // failed.
        cout << "Impossible" << endl;
    } else {
        cout << *min_element(candidate_answer.begin(), candidate_answer.end()) << endl;
    }
    return 0;
}

int main() {
    start = parse_point();
    goal = parse_point();
    cin >> v >> n;
    rep(i, n) {
        Point p = parse_point();
        Real ri, rv;
        cin >> ri >> rv;
        witches.push_back(witch(p, ri, rv));
    }
    cout.precision(12);

    if (n == 1 && 0 < witches[0].r_v && witches[0].r_v < v) {
        return solve_boss();
    }

    Graph g;
    vector<Point> points = {start, goal};
    // direct edge
    g.add_node(start);
    g.add_node(goal);
    g.add_edge(start, goal);
    
    vector<set<Point> > circle_points(n);
    for (auto i = witches.begin(); i != witches.end(); ++i) {
        if (i->r_v > v) continue;
        const int in = i - witches.begin();
        for (auto p = points.begin(); p != points.end(); ++p) { // circle-point edge
            vector<Point> ts = tangents(i->get_circle(0), *p);
            for (auto t = ts.begin(); t != ts.end(); ++t) {
                g.add_edge(*p, *t);
                circle_points[in].insert(*t);
            }
        }
        for (auto j = witches.begin(); j != i; ++j) { // inter-circle edge
            if (j->r_v > v) continue;
            const int jn = j - witches.begin();
            vector<Line> lines = common_tangents(i->get_circle(0), j->get_circle(0));
            for (auto line = lines.begin(); line != lines.end(); ++line) {
                g.add_edge(line->first, line->second);
                circle_points[in].insert(line->first);
                circle_points[jn].insert(line->second);
            }
        }
    }

    for (auto c = circle_points.begin(); c != circle_points.end(); ++c) { // inner-circle edge
        const int ci = c - circle_points.begin();
        const Point pos = witches[ci].pos;
        const Real radius = witches[ci].r_init;
        for (auto j = c->begin(); j != c->end(); ++j) {
            for (auto k = c->begin(); k != j; ++k) {
                const Real deg = angle(*j, *k, pos);
                Real cost = abs(deg * radius);
                bool ok = true;
                for (auto w = witches.begin(); w != witches.end(); ++w) {
                    const int wi = w - witches.begin();
                    if (ci == wi) continue;
                    const Point vect = w->pos - pos;
                    const Point closest = pos + vect / abs(vect) * radius;
                    if (abs(angle(*j, closest, pos)) + abs(angle(*k, closest, pos)) > abs(deg) + eps) {
                        ok &= min(abs(*j - w->pos), abs(*k - w->pos)) > w->r_init;
                    } else {
                        ok &= abs(closest - w->pos) > w->r_init;
                    }
                }
                if (ok) {
                    g.add_arc(*j, *k, cost);
                }
            }
        }
    }

    Real ans = g.shortest_path(start, goal) / v;
    Real timelimit = 1e100;
    for (auto w = witches.begin(); w != witches.end(); ++w) {
        timelimit = min(timelimit, (abs(goal - w->pos) - w->r_init) / w->r_v);
    }
    if (ans > timelimit) {
        cout << "Impossible" << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - 魔女
User amylase
Language C++11 (GCC 4.8.1)
Score 400
Code Size 13701 Byte
Status AC
Exec Time 73 ms
Memory 2352 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 50 / 50 100 / 100 100 / 100 150 / 150
Status
AC × 25
AC × 50
AC × 75
AC × 25
Set Name Test Cases
Subtask1 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt
Subtask2 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt
Subtask3 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt, 31_rand00.txt, 31_rand01.txt, 31_rand02.txt, 31_rand03.txt, 31_rand04.txt, 31_rand05.txt, 31_rand06.txt, 31_rand07.txt, 31_rand08.txt, 31_rand09.txt, 31_rand10.txt, 31_rand11.txt, 31_rand12.txt, 31_rand13.txt, 31_rand14.txt, 31_rand15.txt, 31_rand16.txt, 31_rand17.txt, 31_rand18.txt, 31_rand19.txt, 31_rand20.txt, 31_rand21.txt, 31_rand22.txt, 31_rand23.txt, 31_rand24.txt
Subtask4 41_rand00.txt, 41_rand01.txt, 41_rand02.txt, 41_rand03.txt, 41_rand04.txt, 41_rand05.txt, 41_rand06.txt, 41_rand07.txt, 41_rand08.txt, 41_rand09.txt, 41_rand10.txt, 41_rand11.txt, 41_rand12.txt, 41_rand13.txt, 41_rand14.txt, 41_rand15.txt, 41_rand16.txt, 41_rand17.txt, 41_rand18.txt, 41_rand19.txt, 41_rand20.txt, 41_rand21.txt, 41_rand22.txt, 41_rand23.txt, 41_rand24.txt
Case Name Status Exec Time Memory
11_rand00.txt AC 37 ms 1944 KB
11_rand01.txt AC 38 ms 1944 KB
11_rand02.txt AC 36 ms 1952 KB
11_rand03.txt AC 37 ms 1944 KB
11_rand04.txt AC 34 ms 1944 KB
11_rand05.txt AC 36 ms 1944 KB
11_rand06.txt AC 36 ms 1944 KB
11_rand07.txt AC 34 ms 1944 KB
11_rand08.txt AC 35 ms 1948 KB
11_rand09.txt AC 35 ms 2012 KB
11_rand10.txt AC 36 ms 1948 KB
11_rand11.txt AC 36 ms 1948 KB
11_rand12.txt AC 35 ms 1900 KB
11_rand13.txt AC 34 ms 1948 KB
11_rand14.txt AC 36 ms 1944 KB
11_rand15.txt AC 34 ms 1948 KB
11_rand16.txt AC 36 ms 1940 KB
11_rand17.txt AC 36 ms 1940 KB
11_rand18.txt AC 37 ms 1952 KB
11_rand19.txt AC 34 ms 1948 KB
11_rand20.txt AC 36 ms 1952 KB
11_rand21.txt AC 34 ms 2100 KB
11_rand22.txt AC 34 ms 2072 KB
11_rand23.txt AC 34 ms 1944 KB
11_rand24.txt AC 34 ms 1948 KB
21_rand00.txt AC 35 ms 1952 KB
21_rand01.txt AC 35 ms 1948 KB
21_rand02.txt AC 36 ms 1944 KB
21_rand03.txt AC 71 ms 2332 KB
21_rand04.txt AC 36 ms 1948 KB
21_rand05.txt AC 43 ms 2076 KB
21_rand06.txt AC 35 ms 1952 KB
21_rand07.txt AC 35 ms 1948 KB
21_rand08.txt AC 36 ms 2084 KB
21_rand09.txt AC 36 ms 2076 KB
21_rand10.txt AC 35 ms 1892 KB
21_rand11.txt AC 37 ms 2076 KB
21_rand12.txt AC 68 ms 2332 KB
21_rand13.txt AC 34 ms 1948 KB
21_rand14.txt AC 36 ms 1948 KB
21_rand15.txt AC 40 ms 2080 KB
21_rand16.txt AC 36 ms 1952 KB
21_rand17.txt AC 35 ms 2100 KB
21_rand18.txt AC 36 ms 1952 KB
21_rand19.txt AC 64 ms 2076 KB
21_rand20.txt AC 36 ms 1948 KB
21_rand21.txt AC 35 ms 2072 KB
21_rand22.txt AC 38 ms 2072 KB
21_rand23.txt AC 37 ms 2012 KB
21_rand24.txt AC 35 ms 1948 KB
31_rand00.txt AC 73 ms 2312 KB
31_rand01.txt AC 56 ms 2104 KB
31_rand02.txt AC 60 ms 2352 KB
31_rand03.txt AC 66 ms 2084 KB
31_rand04.txt AC 62 ms 2148 KB
31_rand05.txt AC 51 ms 2012 KB
31_rand06.txt AC 46 ms 1948 KB
31_rand07.txt AC 57 ms 2052 KB
31_rand08.txt AC 46 ms 1960 KB
31_rand09.txt AC 61 ms 2208 KB
31_rand10.txt AC 54 ms 2200 KB
31_rand11.txt AC 55 ms 2072 KB
31_rand12.txt AC 43 ms 2072 KB
31_rand13.txt AC 61 ms 2208 KB
31_rand14.txt AC 49 ms 2076 KB
31_rand15.txt AC 48 ms 2080 KB
31_rand16.txt AC 52 ms 2076 KB
31_rand17.txt AC 39 ms 2076 KB
31_rand18.txt AC 48 ms 2024 KB
31_rand19.txt AC 60 ms 2076 KB
31_rand20.txt AC 36 ms 1944 KB
31_rand21.txt AC 38 ms 1944 KB
31_rand22.txt AC 38 ms 2076 KB
31_rand23.txt AC 39 ms 1944 KB
31_rand24.txt AC 36 ms 1948 KB
41_rand00.txt AC 33 ms 1812 KB
41_rand01.txt AC 33 ms 1968 KB
41_rand02.txt AC 33 ms 1752 KB
41_rand03.txt AC 33 ms 1812 KB
41_rand04.txt AC 33 ms 1820 KB
41_rand05.txt AC 32 ms 1816 KB
41_rand06.txt AC 31 ms 1820 KB
41_rand07.txt AC 32 ms 1816 KB
41_rand08.txt AC 33 ms 1820 KB
41_rand09.txt AC 35 ms 1816 KB
41_rand10.txt AC 36 ms 1820 KB
41_rand11.txt AC 34 ms 1816 KB
41_rand12.txt AC 35 ms 1896 KB
41_rand13.txt AC 34 ms 1972 KB
41_rand14.txt AC 34 ms 1812 KB
41_rand15.txt AC 36 ms 1944 KB
41_rand16.txt AC 35 ms 1948 KB
41_rand17.txt AC 35 ms 1948 KB
41_rand18.txt AC 37 ms 1940 KB
41_rand19.txt AC 36 ms 1940 KB
41_rand20.txt AC 36 ms 2024 KB
41_rand21.txt AC 34 ms 1948 KB
41_rand22.txt AC 34 ms 1824 KB
41_rand23.txt AC 34 ms 1812 KB
41_rand24.txt AC 36 ms 1896 KB