Cod sursa(job #3344848)

Utilizator hrazvanHarsan Razvan hrazvan Data 6 martie 2026 00:54:04
Problema Robot Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6.36 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double INF = 1e18;
const double EPS = 1e-8;

struct Point {
  ll x, y;
  Point() : x(0), y(0) {}
  Point(ll x, ll y) : x(x), y(y) {}
  Point operator+(const Point &o) const { return {x + o.x, y + o.y}; }
  Point operator-(const Point &o) const { return {x - o.x, y - o.y}; }
  bool operator==(const Point &o) const { return x == o.x && y == o.y; }
  bool operator<(const Point &o) const {
    return x < o.x || (x == o.x && y < o.y);
  }
};

ll cross2(Point a, Point b) { return a.x * b.y - a.y * b.x; }

ll det(Point a, Point b, Point c) {
  return (ll)(b.x - a.x) * (c.y - a.y) - (ll)(b.y - a.y) * (c.x - a.x);
}

double dist(Point a, Point b) {
  double dx = a.x - b.x, dy = a.y - b.y;
  return sqrt(dx * dx + dy * dy);
}

typedef vector<Point> Poly;

void ensureCCW(Poly &P) {
  ll area2 = 0;
  int n = P.size();
  for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;
    area2 += P[i].x * P[j].y - P[j].x * P[i].y;
  }
  if (area2 < 0)
    reverse(P.begin(), P.end());
}

void reorder(Poly &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());
}

// Minkowski sum of two convex CCW polygons
Poly minkowskiSum(Poly A, Poly B) {
  reorder(A);
  reorder(B);
  A.push_back(A[0]);
  A.push_back(A[1]);
  B.push_back(B[0]);
  B.push_back(B[1]);
  int sa = A.size() - 2, sb = B.size() - 2;
  int i = 0, j = 0;
  Poly result;
  while (i < sa || j < sb) {
    result.push_back(A[i] + B[j]);
    Point da = A[i + 1] - A[i], db = B[j + 1] - B[j];
    ll cr = cross2(da, db);
    if (cr > 0)
      i++;
    else if (cr < 0)
      j++;
    else {
      i++;
      j++;
    }
  }
  return result;
}

// Check if point p is on segment (a, b) using distance
bool isOnSegment(Point p, Point a, Point b) {
  return fabs(dist(p, a) + dist(p, b) - dist(a, b)) < EPS;
}

// Strict intersection: segments (a,b) and (c,d) properly cross
// (endpoints touching is NOT considered an intersection)
bool intersect(Point a, Point b, Point c, Point d) {
  // Bounding box check
  if (max(min(a.x, b.x), min(c.x, d.x)) > min(max(a.x, b.x), max(c.x, d.x)))
    return false;
  if (max(min(a.y, b.y), min(c.y, d.y)) > min(max(a.y, b.y), max(c.y, d.y)))
    return false;
  ll v1 = 1LL * det(a, b, c) * det(a, b, d);
  ll v2 = 1LL * det(c, d, a) * det(c, d, b);
  if (v1 < 0 && v2 < 0)
    return true;
  return false;
}

// Check if point is strictly inside convex polygon (not on boundary)
// Uses area comparison method from reference
bool inObstacle(Point p, const Poly &poly) {
  int n = poly.size();
  // First check: if p is on any edge, it's NOT strictly inside
  for (int i = 0; i < n; i++) {
    if (isOnSegment(p, poly[i], poly[(i + 1) % n]))
      return false;
  }
  // Compute area of polygon
  ll polyArea = 0;
  for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;
    polyArea += poly[i].x * (ll)poly[j].y - poly[j].x * (ll)poly[i].y;
  }
  polyArea = abs(polyArea);

  // Compute sum of triangle areas (p, poly[i], poly[i+1])
  ll triArea = 0;
  for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;
    ll d = p.x * (ll)poly[i].y + poly[i].x * (ll)poly[j].y +
           poly[j].x * (ll)p.y - p.x * (ll)poly[j].y - poly[i].x * (ll)p.y -
           poly[j].x * (ll)poly[i].y;
    triArea += abs(d);
  }
  return triArea == polyArea;
}

// Check if segment (a, b) is a valid visibility edge:
// - Neither endpoint is strictly inside any obstacle
// - Segment doesn't properly cross any line between two vertices of same
// obstacle
//   (this checks edges AND diagonals, which catches interior passage)
bool isValidLine(Point a, Point b, const vector<Poly> &obstacles, int m) {
  for (int i = 0; i < m; i++) {
    if (inObstacle(a, obstacles[i]) || inObstacle(b, obstacles[i]))
      return false;
    int sz = obstacles[i].size();
    for (int j = 0; j < sz; j++)
      for (int k = j + 1; k < sz; k++)
        if (intersect(a, b, obstacles[i][j], obstacles[i][k]))
          return false;
  }
  return true;
}

int main() {
  freopen("robot.in", "r", stdin);
  freopen("robot.out", "w", stdout);

  int N;
  scanf("%d", &N);
  Poly robot(N);
  for (int i = 0; i < N; i++)
    scanf("%lld %lld", &robot[i].x, &robot[i].y);
  ensureCCW(robot);

  // Anchor = (min_x, min_y) — this is the robot's "position"
  ll minX = robot[0].x, minY = robot[0].y;
  for (auto &p : robot) {
    minX = min(minX, p.x);
    minY = min(minY, p.y);
  }
  // Translate robot so anchor is at origin
  for (auto &p : robot) {
    p.x -= minX;
    p.y -= minY;
  }

  // Reflect robot about origin: negate and reverse to keep CCW
  Poly negRobot(N);
  for (int i = 0; i < N; i++)
    negRobot[i] = Point(-robot[i].x, -robot[i].y);
  reverse(negRobot.begin(), negRobot.end());
  ensureCCW(negRobot);

  int M;
  scanf("%d", &M);
  vector<Poly> obstacles(M);
  for (int i = 0; i < M; i++) {
    int K;
    scanf("%d", &K);
    Poly obs(K);
    for (int j = 0; j < K; j++)
      scanf("%lld %lld", &obs[j].x, &obs[j].y);
    ensureCCW(obs);
    obstacles[i] = minkowskiSum(obs, negRobot);
  }

  ll tx, ty;
  scanf("%lld %lld", &tx, &ty);
  Point start(minX, minY);
  Point goal(tx, ty);

  // Collect nodes: start + all obstacle vertices + goal
  vector<Point> nodes;
  nodes.push_back(start);
  for (int i = 0; i < M; i++)
    for (auto &p : obstacles[i])
      nodes.push_back(p);
  nodes.push_back(goal);

  int nodeCount = nodes.size();

  // Build visibility graph
  vector<vector<pair<int, double>>> adj(nodeCount);
  for (int i = 0; i < nodeCount; i++) {
    for (int j = i + 1; j < nodeCount; j++) {
      if (isValidLine(nodes[i], nodes[j], obstacles, M)) {
        double d = dist(nodes[i], nodes[j]);
        adj[i].push_back({j, d});
        adj[j].push_back({i, d});
      }
    }
  }

  // Dijkstra
  vector<double> best(nodeCount, INF);
  vector<int> seen(nodeCount, 0);
  best[0] = 0;

  for (int iter = 0; iter < nodeCount && !seen[nodeCount - 1]; iter++) {
    int node = -1;
    for (int j = 0; j < nodeCount; j++)
      if (!seen[j] && (node == -1 || best[j] < best[node]))
        node = j;
    if (node == -1 || best[node] >= INF / 2)
      break;
    seen[node] = 1;
    for (auto &[v, w] : adj[node])
      if (best[node] + w < best[v])
        best[v] = best[node] + w;
  }

  if (best[nodeCount - 1] >= INF / 2)
    printf("-1\n");
  else
    printf("%.2f\n", best[nodeCount - 1]);

  return 0;
}