Cod sursa(job #3369994)

Utilizator manutrutaEmanuel Truta manutruta Data 22 octombrie 2026 22:54:03
Problema Robot Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.94 kb
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <queue>
#include <vector>

using namespace std;

struct v2 {
    int x, y;
};

bool operator<(const v2 &a, const v2 &b) {
    return a.x != b.x ? a.x < b.x : a.y < b.y;
}

int cross(v2 o, v2 a, v2 b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

typedef vector<v2> polygon;

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

polygon convex_hull(vector<v2> points) {
    sort(points.begin(), points.end());

    polygon poly;
    for (int i = 0; i < (int)points.size(); i++) {
        while (poly.size() >= 2 &&
               cross(poly[poly.size() - 2], poly.back(), points[i]) <= 0) {
            poly.pop_back();
        }
        poly.push_back(points[i]);
    }
    int first_half_size = poly.size();
    for (int i = points.size() - 2; i >= 0; i--) {
        while ((int)poly.size() > first_half_size &&
               cross(poly[poly.size() - 2], poly.back(), points[i]) <= 0) {
            poly.pop_back();
        }
        poly.push_back(points[i]);
    }
    poly.pop_back();

    return poly;
}

bool crosses(v2 s, v2 e, const polygon &poly) {
    bool left = false, right = false;
    for (const v2 &v : poly) {
        int c = cross(s, e, v);
        left |= c > 0;
        right |= c < 0;
    }
    if (left && right) {
        for (int i = 0; i < (int)poly.size(); i++) {
            v2 a = poly[i], b = poly[(i + 1) % poly.size()];
            if (cross(a, b, s) <= 0 && cross(a, b, e) <= 0) {
                return false;
            }
        }
        return true;
    }
    return false;
}

int main() {
    int n;
    fin >> n;
    polygon robot(n);
    for (v2 &v : robot) {
        fin >> v.x >> v.y;
    }

    int m;
    fin >> m;
    vector<polygon> obstacles(m);
    for (polygon &o : obstacles) {
        fin >> n;
        o.resize(n);
        for (v2 &v : o) {
            fin >> v.x >> v.y;
        }
    }

    v2 goal;
    fin >> goal.x >> goal.y;

    v2 start = robot[0];
    for (v2 &v : robot) {
        start.x = min(start.x, v.x);
        start.y = min(start.y, v.y);
    }
    for (v2 &v : robot) {
        v.x -= start.x;
        v.y -= start.y;
    }

    for (polygon &o : obstacles) {
        vector<v2> expanded_o;
        for (v2 &vo : o) {
            for (v2 &vr : robot) {
                expanded_o.push_back({vo.x - vr.x, vo.y - vr.y});
            }
        }
        o = convex_hull(expanded_o);
    }

    vector<v2> nodes = {start, goal};
    for (polygon &o : obstacles) {
        for (v2 &v : o) {
            nodes.push_back(v);
        }
    }

    vector< vector< pair<int, double> > > g(nodes.size());
    for (int i = 0; i < (int)nodes.size(); i++) {
        for (int j = i + 1; j < (int)nodes.size(); j++) {
            bool clear = true;
            for (polygon &o : obstacles) {
                if (crosses(nodes[i], nodes[j], o)) {
                    clear = false;
                    break;
                }
            }
            if (clear) {
                double length = hypot(
                    nodes[i].x - nodes[j].x,
                    nodes[i].y - nodes[j].y
                );
                g[i].push_back({j, length});
                g[j].push_back({i, length});
            }
        }
    }

    const double inf = 1e18;

    vector<double> dist(nodes.size(), inf);
    dist[0] = 0;

    priority_queue< 
        pair<double, int>, 
        vector< pair<double, int> >,
        greater< pair<double, int> >
    > pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [d, node] = pq.top();
        pq.pop();

        if (dist[node] < d) {
            continue;
        }

        for (auto [v, length] : g[node]) {
            if (dist[v] > d + length) {
                dist[v] = d + length;
                pq.push({dist[v], v});
            }
        }
    }

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

    return 0;
}