Cod sursa(job #3344845)

Utilizator hrazvanHarsan Razvan hrazvan Data 6 martie 2026 00:33:16
Problema Robot Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 7.67 kb
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const double INF = 1e18;

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);
    }
    double dist(const Point &o) const {
        double dx = x - o.x, dy = y - o.y;
        return sqrt(dx * dx + dy * dy);
    }
};

ll cross(Point O, Point A, Point B) {
    return (A.x - O.x) * (ll)(B.y - O.y) - (A.y - O.y) * (ll)(B.x - O.x);
}

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

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 * (ll)P[j].y - P[j].x * (ll)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 = (int)A.size() - 2;
    int sb = (int)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];
        Point 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;
}

// 1 = strictly inside, 0 = on boundary, -1 = outside
int pointInConvexPoly(Point p, const Poly &poly) {
    int n = poly.size();
    bool allPos = true, allNonNeg = true;
    for (int i = 0; i < n; i++) {
        ll c = cross(poly[i], poly[(i + 1) % n], p);
        if (c < 0) { allPos = false; allNonNeg = false; }
        if (c == 0) allPos = false;
    }
    if (allPos) return 1;
    if (allNonNeg) return 0;
    return -1;
}

// Do segments (p1,p2) and (p3,p4) properly intersect?
// Properly = cross interiors. Touching at endpoints or sharing an endpoint is OK.
bool segmentsProperlyIntersect(Point p1, Point p2, Point p3, Point p4) {
    ll d1 = cross(p3, p4, p1);
    ll d2 = cross(p3, p4, p2);
    ll d3 = cross(p1, p2, p3);
    ll d4 = cross(p1, p2, p4);

    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))
        return true;

    // Collinear overlap: interiors of segments overlap
    if (d1 == 0 && d2 == 0) {
        auto strictlyOn = [](Point p, Point a, Point b) -> bool {
            if (p == a || p == b) 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);
        };
        if (strictlyOn(p3, p1, p2)) return true;
        if (strictlyOn(p4, p1, p2)) return true;
        if (strictlyOn(p1, p3, p4)) return true;
        if (strictlyOn(p2, p3, p4)) return true;
    }

    return false;
}

bool segmentHitsObstacles(Point a, Point b, const vector<Poly> &obs) {
    for (auto &poly : obs) {
        int n = poly.size();
        for (int i = 0; i < n; i++) {
            if (segmentsProperlyIntersect(a, b, poly[i], poly[(i + 1) % n]))
                return true;
        }
    }
    return false;
}

// Check if midpoint of (a,b) is strictly inside any obstacle
bool segmentInsideObstacle(Point a, Point b, const vector<Poly> &obs) {
    double mx = (a.x + b.x) / 2.0, my = (a.y + b.y) / 2.0;
    for (auto &poly : obs) {
        int n = poly.size();
        bool inside = true;
        for (int i = 0; i < n; i++) {
            int j = (i + 1) % n;
            double cx = (poly[j].x - poly[i].x) * (my - poly[i].y) -
                        (poly[j].y - poly[i].y) * (mx - poly[i].x);
            if (cx <= 0) { inside = false; break; }
        }
        if (inside) return true;
    }
    return false;
}

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), translate robot so anchor is at origin
    ll minX = robot[0].x, minY = robot[0].y;
    for (auto &p : robot) {
        minX = min(minX, p.x);
        minY = min(minY, p.y);
    }
    for (auto &p : robot) {
        p.x -= minX;
        p.y -= minY;
    }

    // Reflect robot: negate then 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(0, 0);
    Point goal(tx, ty);

    // Check feasibility
    for (auto &obs : obstacles) {
        if (pointInConvexPoly(start, obs) == 1) {
            printf("-1\n");
            return 0;
        }
        if (pointInConvexPoly(goal, obs) == 1) {
            printf("-1\n");
            return 0;
        }
    }

    // Collect vertices: start, goal, + obstacle vertices not strictly inside another
    vector<Point> points;
    points.push_back(start);
    points.push_back(goal);

    for (int i = 0; i < M; i++) {
        for (auto &p : obstacles[i]) {
            bool inside = false;
            for (int j = 0; j < M; j++) {
                if (i == j) continue;
                if (pointInConvexPoly(p, obstacles[j]) == 1) {
                    inside = true;
                    break;
                }
            }
            if (!inside)
                points.push_back(p);
        }
    }

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

    int np = points.size();
    vector<vector<pair<int, double>>> adj(np);

    // Build visibility graph
    for (int i = 0; i < np; i++) {
        for (int j = i + 1; j < np; j++) {
            if (segmentHitsObstacles(points[i], points[j], obstacles))
                continue;
            if (segmentInsideObstacle(points[i], points[j], obstacles))
                continue;
            double d = points[i].dist(points[j]);
            adj[i].push_back({j, d});
            adj[j].push_back({i, d});
        }
    }

    // Dijkstra
    int si = find(points.begin(), points.end(), start) - points.begin();
    int gi = find(points.begin(), points.end(), goal) - points.begin();

    vector<double> dist(np, INF);
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;
    dist[si] = 0;
    pq.push({0, si});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u] + 1e-9) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v] - 1e-9) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    if (dist[gi] >= INF / 2) {
        printf("-1\n");
    } else {
        printf("%.2f\n", dist[gi]);
    }

    return 0;
}