| c++ source |
| #include <bits/stdc++.h> |
| using namespace std; |
| #define sz(x) ((int) (x).size()) |
| typedef long long ll; |
| typedef long double ld; |
| const int INF = 1000001000; |
| const ll INFL = 2000000000000001000; |
| int solve(); |
| int main() |
| { |
| srand(2317); |
| cout.precision(10); |
| cout.setf(ios::fixed); |
| #ifdef LOCAL |
| freopen("d.in", "r", stdin); |
| #else |
| #endif |
| int tn = 1; |
| for (int i = 0; i < tn; ++i) |
| solve(); |
| #ifdef LOCAL |
| cerr << "Time: " << double(clock()) / CLOCKS_PER_SEC << ' '; |
| #endif |
| } |
| const int MAGIC = 12354; |
| struct Point |
| { |
| int x, y; |
| Point(): x(0), y(0) {} |
| Point(int x, int y): x(x), y(y) {} |
| Point operator-(const Point &b) const |
| { |
| return Point(x - b.x, y - b.y); |
| } |
| inline bool upper() const |
| { |
| return y > 0 || (x > 0 && y == 0); |
| } |
| inline bool upper(const Point &p) const |
| { |
| ll pr = *this * p; |
| if (pr != 0) |
| return pr > 0; |
| pr = *this % p; |
| return pr > 0; |
| } |
| ll operator*(const Point &a) const |
| { |
| return ll(x) * ll(a.y) - ll(y) * ll(a.x); |
| } |
| ll operator%(const Point &a) const |
| { |
| return ll(x) * ll(a.x) + ll(y) * ll(a.y); |
| } |
| ld abs() |
| { |
| return sqrtl(ld(x) * ld(x) + ld(y) * ld(y)); |
| } |
| explicit operator bool() const |
| { |
| return x != 0 || y != 0; |
| } |
| }; |
| struct ldPoint |
| { |
| ld x, y; |
| ldPoint(): x(0), y(0) {} |
| ldPoint(Point p): x(p.x), y(p.y) {} |
| ldPoint(ld x, ld y): x(x), y(y) {} |
| ldPoint operator-(const ldPoint &b) const |
| { |
| return ldPoint(x - b.x, y - b.y); |
| } |
| ld operator*(const ldPoint &a) const |
| { |
| return x * a.y - y * a.x; |
| } |
| ld operator%(const ldPoint &a) const |
| { |
| return x * a.x + y * a.y; |
| } |
| ld abs() |
| { |
| return sqrtl(ld(x) * ld(x) + ld(y) * ld(y)); |
| } |
| }; |
| ostream &operator<<(ostream &out, Point pt) |
| { |
| out << '(' << pt.x << ", " << pt.y << ')'; |
| return out; |
| } |
| bool lower_angle(const Point &a, const Point &b) |
| { |
| if (a.x == MAGIC) |
| return false; |
| if (b.x == MAGIC) |
| return true; |
| bool ua = a.upper(), ub = b.upper(); |
| if (ua ^ ub) |
| return ua; |
| return a * b > 0; |
| } |
| ldPoint intersect(ldPoint a, ldPoint b, ldPoint c, ldPoint d, bool assertion = false) |
| { |
| #ifdef LOCAL |
| if (assertion) |
| { |
| ld pr1 = (d - c) * (a - c); |
| ld pr2 = (d - c) * (b - c); |
| assert(!(pr1 < 0 && pr2 < 0)); |
| assert(!(pr1 > 0 && pr2 > 0)); |
| } |
| #endif |
| ld s1 = (c - a) * (d - a); |
| ld s2 = (b - a) * (d - c); |
| ld x = ld(a.x) + ld(b.x - a.x) * s1 / s2; |
| ld y = ld(a.y) + ld(b.y - a.y) * s1 / s2; |
| return ldPoint(x, y); |
| } |
| struct Wall |
| { |
| Point a, b; |
| Wall() {} |
| Wall(Point a, Point b): a(a), b(b) {} |
| }; |
| struct SlowHull |
| { |
| vector <Wall> line; |
| Point l, r; |
| bool fictive; |
| SlowHull(): fictive(true) {} |
| ld get(Point p) |
| { |
| if (fictive) |
| return 1e18; |
| assert(l * r >= 0); |
| ld res = 1e18; |
| for (auto &wall: line) |
| res = min(res, intersect(wall.a, wall.b, Point(0, 0), p, true).abs()); |
| return res; |
| } |
| void push(Wall p) |
| { |
| fictive = false; |
| assert(l * r >= 0); |
| if (p.a * l >= 0 && r * p.b >= 0) |
| line.push_back(p); |
| } |
| }; |
| bool lower_angle_ld(const ldPoint &a, const ldPoint &b) |
| { |
| return a * b > 0; |
| } |
| bool equal_angle(const Point &a, const Point &b) |
| { |
| bool ua = a.upper(), ub = b.upper(); |
| if (ua ^ ub) |
| return false; |
| return a * b == 0; |
| } |
| bool lower_line(const Wall &w1, const Wall &w2) |
| { |
| Point a = w1.b - w1.a; |
| Point b = w2.b - w2.a; |
| ll pr = a * b; |
| if (pr) |
| return pr > 0; |
| ld dist1 = fabsl(w1.a * w1.b) / a.abs(); |
| ld dist2 = fabsl(w2.a * w2.b) / b.abs(); |
| return dist1 < dist2; |
| } |
| struct OfflineHull |
| { |
| vector <Wall> line; |
| vector <Wall> o; |
| vector <ldPoint> pt; |
| Point l, r; |
| OfflineHull(Point l, Point r): l(l), r(r) {} |
| ld get(Point p) |
| { |
| if (line.empty()) |
| return 1e18; |
| int pos = lower_bound(pt.begin(), pt.end(), ldPoint(p), lower_angle_ld) - pt.begin(); |
| ld res = intersect(o[pos].a, o[pos].b, ldPoint(0, 0), ldPoint(p), true).abs(); |
| return res; |
| } |
| void add_wall(Wall &wall) |
| { |
| if (!o.empty() && (wall.b - wall.a) * (o.back().b - o.back().a) == 0) |
| return; |
| while (!pt.empty()) |
| { |
| if ((ldPoint(wall.b) - ldPoint(wall.a)) * (pt.back() - ldPoint(wall.a)) > 0) |
| break; |
| pt.pop_back(); |
| o.pop_back(); |
| } |
| if (!o.empty()) |
| pt.push_back(intersect(wall.a, wall.b, o.back().a, o.back().b)); |
| o.push_back(wall); |
| } |
| void build() |
| { |
| sort(line.begin(), line.end(), lower_line); |
| o.clear(); |
| pt.clear(); |
| for (auto &wall: line) |
| add_wall(wall); |
| } |
| void clear() |
| { |
| line.clear(); |
| o.clear(); |
| pt.clear(); |
| } |
| void push(Wall p) |
| { |
| assert(l * r >= 0); |
| if (p.a * l >= 0 && r * p.b >= 0) |
| line.push_back(p); |
| } |
| }; |
| struct Hull |
| { |
| vector <OfflineHull> o; |
| int lines; |
| Point l, r; |
| Hull(): lines(0) {} |
| ld get(Point p) |
| { |
| ld res = 1e18; |
| for (int i = 0; i < sz(o); ++i) |
| res = min(res, o[i].get(p)); |
| //~ cout << "DEBUG " << res << ' '; |
| return res; |
| } |
| void simple_push(Wall w) |
| { |
| if (lines == 0) |
| o.push_back(OfflineHull(l, r)); |
| o[0].push(w); |
| o[0].build(); |
| } |
| void push(Wall w) |
| { |
| //~ simple_push(w); |
| int bit = 0; |
| while ((1 << bit) & lines) |
| ++bit; |
| if (bit >= sz(o)) |
| o.push_back(OfflineHull(l, r)); |
| assert(bit < sz(o)); |
| for (int i = 0; i < bit; ++i) |
| { |
| for (int j = 0; j < sz(o[i].line); ++j) |
| o[bit].push(o[i].line[j]); |
| o[i].clear(); |
| } |
| o[bit].push(w); |
| o[bit].build(); |
| ++lines; |
| } |
| }; |
| const int base = (1 << 18); |
| Hull tree[base * 2]; |
| struct Query |
| { |
| vector <Point> v; |
| bool wall; |
| }; |
| vector <Query> query; |
| vector <Point> angle; |
| vector <ld> angle_best; |
| void build_wall(int l, int r, Wall &w, int v = 1, int cl = 0, int cr = base) |
| { |
| if (l <= cl && cr <= r) |
| { |
| tree[v].push(w); |
| return; |
| } |
| if (r <= cl || cr <= l) |
| return; |
| int cc = (cl + cr) / 2; |
| build_wall(l, r, w, v * 2, cl, cc); |
| build_wall(l, r, w, v * 2 + 1, cc, cr); |
| } |
| ld shot(int v) |
| { |
| ld res = 1e18; |
| res = min(res, angle_best[v]); |
| Point ang = angle[v]; |
| v += base; |
| while (v) |
| { |
| res = min(res, tree[v].get(ang)); |
| v /= 2; |
| } |
| return res; |
| } |
| int lower_pos(Point p) |
| { |
| int res = lower_bound(angle.begin(), angle.end(), p, lower_angle) - angle.begin(); |
| assert(res < sz(angle) && equal_angle(p, angle[res])); |
| return res; |
| } |
| int upper_pos(Point p) |
| { |
| int res = upper_bound(angle.begin(), angle.end(), p, lower_angle) - angle.begin(); |
| return res; |
| } |
| int solve() |
| { |
| char tmp[10]; |
| while (true) |
| { |
| scanf("%s", tmp); |
| if (strcmp(tmp, "shot") == 0) |
| { |
| int x, y; |
| scanf("%d%d", &x, &y); |
| Query q; |
| q.v.push_back(Point(x, y)); |
| q.wall = false; |
| query.push_back(q); |
| angle.push_back(Point(x, y)); |
| } |
| else if (strcmp(tmp, "wall") == 0) |
| { |
| int x1, y1, x2, y2; |
| scanf("%d%d%d%d", &x1, &y1, &x2, &y2); |
| Query q; |
| q.v.push_back(Point(x1, y1)); |
| q.v.push_back(Point(x2, y2)); |
| q.wall = true; |
| query.push_back(q); |
| angle.push_back(Point(x1, y1)); |
| angle.push_back(Point(x2, y2)); |
| } |
| else |
| break; |
| } |
| angle.push_back(Point(1, 0)); |
| angle.push_back(Point(-1, 0)); |
| angle.push_back(Point(0, 1)); |
| angle.push_back(Point(0, -1)); |
| sort(angle.begin(), angle.end(), lower_angle); |
| angle.resize(unique(angle.begin(), angle.end(), equal_angle) - angle.begin()); |
| angle_best.resize(sz(angle), 1e18); |
| for (int i = 0; i < sz(angle); ++i) |
| tree[i + base].r = tree[i + base].l = angle[i]; |
| for (int i = base - 1; i > 0; --i) |
| { |
| tree[i].l = tree[i * 2].l; |
| tree[i].r = tree[i * 2 + 1].r; |
| } |
| //~ for (auto x: angle) |
| //~ cerr << x << ' '; |
| for (auto &q: query) |
| { |
| if (q.wall) |
| { |
| Point a = q.v[0]; |
| Point b = q.v[1]; |
| if (a * b < 0) |
| swap(a, b); |
| Wall w(a, b); |
| int a_pos = lower_pos(a); |
| int b_pos_2 = lower_pos(b); |
| int b_pos = upper_pos(b); |
| angle_best[a_pos] = min(angle_best[a_pos], a.abs()); |
| angle_best[b_pos_2] = min(angle_best[b_pos_2], b.abs()); |
| if (a_pos > b_pos) |
| { |
| build_wall(a_pos, sz(angle), w); |
| build_wall(0, b_pos, w); |
| } |
| else |
| build_wall(a_pos, b_pos, w); |
| } |
| else |
| { |
| int pos = lower_pos(q.v[0]); |
| ld res = shot(pos); |
| if (res >= 1e18) |
| cout << "Infinite "; |
| else |
| cout << res / q.v[0].abs() << ' '; |
| } |
| } |
| return 0; |
| } |
Комментарии