Cod sursa(job #3375352)

Utilizator SkibidiCezarCezar Bolba SkibidiCezar Data 11 noiembrie 2026 14:01:04
Problema Robot Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.06 kb
#include <bits/stdc++.h>

using namespace std;
using ld = long double;
ifstream fin ("robot.in");
ofstream fout ("robot.out");
int n, m, p;
struct punct{ //il folosesc si pentru vector
    ld x, y;
};
punct st, streal, fn, aux;
punct r[15], rv[15];
vector <punct> ob[30], obv[30];
vector <punct> a;
vector <ld> d;
vector <vector <int>> v;

ld determinant(punct a, punct b, punct c){
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

bool cmp(punct a, punct b){
    if(a.y <= 0 && b.y > 0) return 1;
    if(a.y > 0 && b.y <= 0) return 0;
    return determinant({0, 0}, a, b) >= 0;
}

bool intersectie(punct a1, punct b1, punct a2, punct b2){
    if(determinant(a1, a2, b1) * determinant(a1, b2, b1) >= 0){
        return 0;
    }
    if(determinant(a2, a1, b2) * determinant(a2, b1, b2) >= 0){
        return 0;
    }
    return 1;
}

ld dist(punct a, punct b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void dijkstra(){
    priority_queue <pair <ld, int>, vector <pair <ld, int>>, greater <pair <ld, int>>> pq;
    pq.push({0, 0});
    int nod, nxt;
    ld dnod, dnxt;
    while(!pq.empty()){
        nod = pq.top().second;
        dnod = pq.top().first;
        pq.pop();
        if(d[nod] < dnod) continue;
        for(int i = 0; i < v[nod].size(); i++){
            nxt = v[nod][i];
            dnxt = dnod + dist(a[nod], a[nxt]);
            if(d[nxt] == -1 || dnxt < d[nxt]){
                cout << a[nod].x << " " << a[nod].y << " " << dnod << " " << a[nxt].x << " " << a[nxt].y << " " << dnxt << "\n";
                d[nxt] = dnxt;
                pq.push({dnxt, nxt});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    fin >> n;
    st = streal = {5001.0, 5001.0};
    for(int i = 1; i <= n; i++){
        fin >> r[i].x >> r[i].y;
        st.x = min(st.x, r[i].x);
        st.y = min(st.y, r[i].y);
        if(r[i].y < streal.y) streal = r[i];
        if(i > 1) rv[i] = {r[i-1].x - r[i].x, r[i-1].y - r[i].y};
        //la robot ne trebuie in sens orar vectorii
    }
    a.push_back(streal);
    d.push_back(0);
    rv[1] = {r[n].x - r[1].x, r[n].y - r[1].y};
    fin >> m;
    for(int i = 1; i <= m; i++){
        fin >> p;
        ob[i].resize(p);
        obv[i].resize(p);
        aux = {-5001.0, -5001.0};
        for(int j = 0; j < p; j++){
            fin >> ob[i][j].x >> ob[i][j].y;
            if(ob[i][j].y > aux.y) aux = ob[i][j];
            if(j > 0) obv[i][j] = {ob[i][j].x - ob[i][j-1].x, ob[i][j].y - ob[i][j-1].y};
            //la obstacole ne trebuie in sens trigo vectorii
        }
        obv[i][0] = {ob[i][0].x - ob[i][p-1].x, ob[i][0].y - ob[i][p-1].y};
        for(int j = 1; j <= n; j++){
            obv[i].push_back(rv[j]);
        }
        sort(obv[i].begin(), obv[i].end(), cmp);
        ob[i].resize(obv[i].size());
        for(int j = 0; j < ob[i].size(); j++){
            ob[i][j] = aux;
            a.push_back(ob[i][j]);
            d.push_back(-1);
            aux.x += obv[i][j].x;
            aux.y += obv[i][j].y;
        }
    }
    fin >> fn.x >> fn.y;
    fn.x += streal.x - st.x;
    a.push_back(fn);
    d.push_back(-1);
    v.resize(a.size());
    for(int i = 0; i < a.size(); i++){
        for(int j = 0; j < a.size(); j++){
            bool inter = 1;
            if(i != j){
                for(int ii = 1; ii <= m; ii++){
                    for(int jj = 0; jj < ob[ii].size() - 1; jj++){
                        if(intersectie(a[i], a[j], ob[ii][jj], ob[ii][jj+1])){
                            inter = 0;
                            break;
                        }
                    }
                    if(intersectie(a[i], a[j], ob[ii].back(), ob[ii][0])){
                        inter = 0;
                    }
                    if(!inter) break;
                }
                if(inter){
                    v[i].push_back(j);
                }
            }
        }
    }
    dijkstra();
    fout << d.back();
    return 0;
}