Cod sursa(job #3344843)

Utilizator hrazvanHarsan Razvan hrazvan Data 6 martie 2026 00:02:09
Problema Robot Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.56 kb
#include <bits/stdc++.h>

using namespace std;

struct Point {
  int x, y;
  bool operator==(const Point &other) const {
    return x == other.x && y == other.y;
  }
  bool operator<(const Point &other) const {
    return x < other.x || (x == other.x && y < other.y);
  }
  double dist(const Point &other) const {
    return std::sqrt((double)(x - other.x) * (x - other.x) +
                     (double)(y - other.y) * (y - other.y));
  }
};

struct Line {
  Point a, b;
  double angle_;
  Line(Point a, Point b)
      : a(a), b(b), angle_(std::atan2(b.y - a.y, b.x - a.x)) {}

  bool operator<(const Line &other) const { return angle_ < other.angle_; }
};

int main() {
  freopen("robot.in", "r", stdin);
  freopen("robot.out", "w", stdout);
  int n;
  cin >> n;
  using Shape = vector<Point>;
  Shape r(n);
  for (int i = 0; i < n; i++) {
    cin >> r[i].x >> r[i].y;
  }

  auto cross = [](Point o, Point a, Point b) -> long long {
    return (long long)(a.x - o.x) * (b.y - o.y) -
           (long long)(a.y - o.y) * (b.x - o.x);
  };

  auto collide = [&](const Shape &R, const Shape &obstacle) -> Shape {
    int rn = R.size();
    Shape nr(rn);
    for (int i = 0; i < rn; i++)
      nr[i] = {-R[i].x, -R[i].y};

    auto reorder = [](Shape &P) {
      int pos = 0;
      for (int i = 1; i < (int)P.size(); i++) {
        if (P[i].y < P[pos].y || (P[i].y == P[pos].y && P[i].x < P[pos].x))
          pos = i;
      }
      rotate(P.begin(), P.begin() + pos, P.end());
    };

    Shape A = nr, B = obstacle;
    reorder(A);
    reorder(B);

    A.push_back(A[0]);
    A.push_back(A[1]);
    B.push_back(B[0]);
    B.push_back(B[1]);

    Shape result;
    int i = 0, j = 0;
    int sa = (int)A.size() - 2, sb = (int)B.size() - 2;
    while (i < sa || j < sb) {
      result.push_back({A[i].x + B[j].x, A[i].y + B[j].y});
      Point da = {A[i + 1].x - A[i].x, A[i + 1].y - A[i].y};
      Point db = {B[j + 1].x - B[j].x, B[j + 1].y - B[j].y};
      long long cr = (long long)da.x * db.y - (long long)da.y * db.x;
      if (cr >= 0 && i < sa)
        ++i;
      if (cr <= 0 && j < sb)
        ++j;
    }
    return result;
  };

  auto get_lines = [](const Shape &sh) -> vector<Line> {
    vector<Line> res;
    int sz = sh.size();
    for (int i = 0; i < sz; i++)
      res.emplace_back(sh[i], sh[(i + 1) % sz]);
    return res;
  };

  int m;
  cin >> m;
  std::vector<Shape> s(m);
  for (int i = 0; i < m; i++) {
    int k;
    cin >> k;
    Shape obstacle(k);
    for (int j = 0; j < k; j++) {
      cin >> obstacle[j].x >> obstacle[j].y;
    }
    s[i] = collide(r, obstacle);
  }

  auto strictly_inside = [&](Point p) -> bool {
    for (auto &poly : s) {
      int sz = poly.size();
      bool inside = true;
      for (int i = 0; i < sz; i++) {
        if (cross(poly[i], poly[(i + 1) % sz], p) <= 0) {
          inside = false;
          break;
        }
      }
      if (inside)
        return true;
    }
    return false;
  };

  auto intersects = [&](const Line &seg, const vector<Line> &edges) -> bool {
    for (auto &e : edges) {
      long long d1 = cross(seg.a, seg.b, e.a);
      long long d2 = cross(seg.a, seg.b, e.b);
      long long d3 = cross(e.a, e.b, seg.a);
      long long d4 = cross(e.a, e.b, seg.b);
      if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
          ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))
        return true;
    }
    return false;
  };

  auto midpoint_strictly_inside = [&](Point u, Point v) -> bool {
    int mx2 = u.x + v.x, my2 = u.y + v.y;
    for (auto &poly : s) {
      int sz = poly.size();
      bool inside = true;
      for (int i = 0; i < sz; i++) {
        Point a = poly[i], b = poly[(i + 1) % sz];
        long long cr = (long long)(b.x - a.x) * (my2 - 2 * a.y) -
                       (long long)(b.y - a.y) * (mx2 - 2 * a.x);
        if (cr <= 0) { // <= 0, not < 0
          inside = false;
          break;
        }
      }
      if (inside)
        return true;
    }
    return false;
  };

  std::vector<Point> points;
  points.emplace_back(0, 0);
  int x, y;
  cin >> x >> y;

  if (strictly_inside(Point{0, 0}) || strictly_inside(Point{x, y})) {
    cout << -1 << '\n';
    return 0;
  }

  points.emplace_back(Point{x, y});
  for (int i = 0; i < m; i++) {
    for (auto p : s[i]) {
      if (!strictly_inside(p)) {
        points.emplace_back(p);
      }
    }
  }

  sort(points.begin(), points.end());
  points.erase(unique(points.begin(), points.end()), points.end());

  std::vector<Line> lines;
  for (int i = 0; i < m; i++) {
    auto slines = get_lines(s[i]);
    lines.insert(lines.end(), slines.begin(), slines.end());
  }
  std::map<Point, std::vector<Point>> adj;
  for (int i = 0; i < (int)points.size(); i++) {
    for (int j = i + 1; j < (int)points.size(); j++) {
      Point u = points[i], v = points[j];
      if (!intersects(Line{u, v}, lines) && !midpoint_strictly_inside(u, v)) {
        adj[u].push_back(v);
        adj[v].push_back(u);
      }
    }
  }

  // Dijkstra
  std::priority_queue<std::pair<double, Point>,
                      std::vector<std::pair<double, Point>>,
                      std::greater<std::pair<double, Point>>>
      pq;
  pq.push({0, Point{0, 0}});
  std::map<Point, double> dist;
  dist[Point{0, 0}] = 0;
  while (!pq.empty()) {
    auto [d, u] = pq.top();
    pq.pop();
    if (d > dist[u])
      continue;
    for (auto v : adj[u]) {
      if (dist.find(v) == dist.end() || dist[v] > d + u.dist(v)) {
        dist[v] = d + u.dist(v);
        pq.push({dist[v], v});
      }
    }
  }
  if (dist.find(Point{x, y}) == dist.end()) {
    cout << -1 << '\n';
  } else {
    cout << fixed << setprecision(2) << dist[Point{x, y}] << '\n';
  }
  return 0;
}