Cod sursa(job #3344844)

Utilizator hrazvanHarsan Razvan hrazvan Data 6 martie 2026 00:13:10
Problema Robot Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6.02 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 onSegment = [&](Point a, Point b, Point p) -> bool {
    if (cross(a, b, p) != 0) return false;
    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
  };

  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;

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

      // allow touching at endpoints
      if (seg.a == e.a || seg.a == e.b || seg.b == e.a || seg.b == e.b)
        continue;

      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;

      if (d1 == 0 && onSegment(seg.a, seg.b, e.a)) return true;
      if (d2 == 0 && onSegment(seg.a, seg.b, e.b)) return true;
      if (d3 == 0 && onSegment(e.a, e.b, seg.a)) return true;
      if (d4 == 0 && onSegment(e.a, e.b, seg.b)) 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) {
          inside = false;
          break;
        }
      }

      if (inside) return true;
    }

    return false;
  };

  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());

  vector<Line> lines;

  for (int i = 0; i < m; i++) {
    auto slines = get_lines(s[i]);
    lines.insert(lines.end(), slines.begin(), slines.end());
  }

  map<Point, 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);
      }
    }
  }

  priority_queue<pair<double, Point>,
                 vector<pair<double, Point>>,
                 greater<pair<double, Point>>> pq;

  pq.push({0, Point{0, 0}});

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