Cod sursa(job #3358613)

Utilizator rares89_Dumitriu Rares rares89_ Data 18 iunie 2026 16:45:03
Problema Robot Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6.86 kb
#include <bits/stdc++.h>

using namespace std;
using PA = pair<double, int>;

ifstream fin("robot.in");
ofstream fout("robot.out");

struct Point {
    long long x, y;
    bool operator==(const Point& o) const {
        return x == o.x && y == o.y;
    }
};

int sgn(long long x) {
    return (x > 0) - (x < 0);
}

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

bool strict_intersect(Point A, Point B, Point C, Point D) {
    int s1 = sgn(cross(A, B, C));
    int s2 = sgn(cross(A, B, D));
    int s3 = sgn(cross(C, D, A));
    int s4 = sgn(cross(C, D, B));
    return (s1 != 0 && s2 != 0 && s1 != s2 && s3 != 0 && s4 != 0 && s3 != s4);
}

bool on_segment(Point A, Point B, Point P) {
    if (cross(A, B, P) != 0) {
        return false;
    }
    return P.x >= min(A.x, B.x) && P.x <= max(A.x, B.x) &&
           P.y >= min(A.y, B.y) && P.y <= max(A.y, B.y);
}

vector<Point> convex_hull(vector<Point>& pts) {
    if (pts.size() <= 2) return pts;
    sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    vector<Point> hull;
    for (int i = 0; i < pts.size(); i++) {
        while (hull.size() >= 2) {
            Point p1 = hull[hull.size() - 2];
            Point p2 = hull[hull.size() - 1];
            if (cross(p1, p2, pts[i]) <= 0) {
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(pts[i]);
    }
    int lower_sz = hull.size();
    for (int i = (int)pts.size() - 2; i >= 0; i--) {
        while (hull.size() > lower_sz) {
            Point p1 = hull[hull.size() - 2];
            Point p2 = hull[hull.size() - 1];
            if (cross(p1, p2, pts[i]) <= 0) {
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(pts[i]);
    }
    hull.pop_back();
    return hull;
}

int n, m;
vector<Point> robot;
vector<vector<Point>> obstacles;

bool is_visible(Point A, Point B) {
    for (auto& poly : obstacles) {
        int sz = poly.size();
        for (int i = 0; i < sz; i++) {
            if (strict_intersect(A, B, poly[i], poly[(i + 1) % sz])) {
                return false;
            }
        }
    }

    vector<Point> pts;
    pts.push_back(A);
    pts.push_back(B);
    vector<int> check_polys;
    for (int k = 0; k < obstacles.size(); k++) {
        bool has_v = false;
        for (auto& p : obstacles[k]) {
            if (on_segment(A, B, p)) {
                has_v = true;
                pts.push_back(p);
            }
        }
        if (has_v) {
            check_polys.push_back(k);
        }
    }

    sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });

    vector<Point> u;
    u.push_back(pts[0]);
    for (int i = 1; i < pts.size(); i++) {
        if (pts[i].x != u.back().x || pts[i].y != u.back().y) {
            u.push_back(pts[i]);
        }
    }

    for (int i = 0; i < (int)u.size() - 1; i++) {
        Point M;
        M.x = u[i].x + u[i + 1].x;
        M.y = u[i].y + u[i + 1].y;

        for (int k : check_polys) {
            auto& poly = obstacles[k];
            if (poly.size() < 3) continue;
            bool strictly_inside = true;
            int sz = poly.size();
            for (int j = 0; j < sz; j++) {
                Point p1 = poly[j], p2 = poly[(j + 1) % sz];
                long long vx = 2LL * p2.x - 2LL * p1.x;
                long long vy = 2LL * p2.y - 2LL * p1.y;
                long long px = M.x - 2LL * p1.x;
                long long py = M.y - 2LL * p1.y;
                if (vx * py - vy * px <= 0) {
                    strictly_inside = false;
                    break;
                }
            }
            if (strictly_inside) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    fin >> n;
    long long minX = 1e18, minY = 1e18;
    for (int i = 0; i < n; i++) {
        long long x, y;
        fin >> x >> y;
        robot.push_back({x, y});
        minX = min(minX, x);
        minY = min(minY, y);
    }

    vector<Point> neg_R0;
    for (int i = 0; i < n; i++) {
        neg_R0.push_back({-(robot[i].x - minX), -(robot[i].y - minY)});
    }

    fin >> m;
    for (int i = 0; i < m; i++) {
        int p;
        fin >> p;
        vector<Point> O;
        for (int j = 0; j < p; j++) {
            long long x, y;
            fin >> x >> y;
            O.push_back({x, y});
        }
        vector<Point> pts;
        for (int j = 0; j < p; j++) {
            for (int k = 0; k < n; k++) {
                pts.push_back({O[j].x + neg_R0[k].x, O[j].y + neg_R0[k].y});
            }
        }
        obstacles.push_back(convex_hull(pts));
    }

    long long ex, ey;
    fin >> ex >> ey;
    Point S = {minX, minY};
    Point E = {ex, ey};
    fin.close();

    vector<Point> nodes;
    nodes.push_back(S);
    nodes.push_back(E);
    for (auto& poly : obstacles) {
        for (auto& p : poly) {
            nodes.push_back(p);
        }
    }

    sort(nodes.begin(), nodes.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    auto it = unique(nodes.begin(), nodes.end());
    nodes.erase(it, nodes.end());

    int start_idx = -1, end_idx = -1;
    for (int i = 0; i < nodes.size(); i++) {
        if (nodes[i] == S) start_idx = i;
        if (nodes[i] == E) end_idx = i;
    }

    int N_nodes = nodes.size();
    vector<vector<pair<int, double>>> adj(N_nodes);

    for (int i = 0; i < N_nodes; i++) {
        for (int j = i + 1; j < N_nodes; j++) {
            if (is_visible(nodes[i], nodes[j])) {
                double d = hypot(nodes[i].x - nodes[j].x, nodes[i].y - nodes[j].y);
                adj[i].push_back({j, d});
                adj[j].push_back({i, d});
            }
        }
    }

    vector<double> dist(N_nodes, 1e18);
    priority_queue<PA, vector<PA>, greater<PA>> Q;

    dist[start_idx] = 0;
    Q.push({0, start_idx});

    while (!Q.empty()) {
        double d = Q.top().first;
        int u = Q.top().second;
        Q.pop();

        if (d > dist[u]) continue;
        if (u == end_idx) break;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            double w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                Q.push({dist[v], v});
            }
        }
    }

    if (dist[end_idx] == 1e18) {
        fout << "-1\n";
    } else {
        fout << fixed << setprecision(2) << dist[end_idx] << "\n";
    }
    fout.close();

    return 0;
}