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