Cod sursa(job #2161732)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 11 martie 2018 20:30:24
Problema Robot Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 5.76 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

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

const int nmax = 25;
const int pmax = 1000;

struct pct {
    double x, y;

    pct () {}
    pct (double _x, double _y) {
        x = _x, y = _y;
    }

    pct operator + (const pct &shp) const {
        return pct(x + shp.x, y + shp.y);
    }
    pct operator - (const pct &shp) const {
        return pct(x - shp.x, y - shp.y);
    }
    pct operator * (const pct &shp) const {
        return pct (x * shp.x - y * shp.y, y * shp.x + x * shp.y);
    }
};

pct conj (pct a) {
    return pct(a.x, -a.y);
}
double real (pct a) {
    return a.x;
}
double imag (pct a) {
    return a.y;
}

struct Heap_node {
    int x; double val;

    Heap_node () {}
    Heap_node (int _x, double _val) {
        x = _x, val = _val;
    }

    bool operator < (const Heap_node &shp) const {
        return val > shp.val;
    }
};
priority_queue< Heap_node > heap;

bool gata[pmax + 1];
double d[pmax + 1];

int m, nrnoduri;
pct destinatie, centru_obs;

pct cine[pmax + 1];
vector< pct > robot;
vector< pct > obs[nmax + 1];

vector< pair<int, double> > g[pmax + 1];

double dot (pct a, pct b) {
    return real(conj(a) * b);
}

double cross (pct a, pct b) {
    return imag(conj(a) * b);
}

double det (pct a, pct b, pct c) {
    return cross(b - a, c - a);
}

bool cmp (pct a, pct b) {
    if (real(a) == real(b) && real(a) == real(centru_obs)) {
        return imag(a) < imag(b);
    }

    return det(centru_obs, a, b) > 0;
}

vector< pct > mareste(vector< pct > poli) {
    vector< pct > ans;
    for (auto i : poli) {
        for (auto j : robot) {
            ans.push_back(robot[ 0 ] + i - j);
        }
    }

    for (int i = 1; i < (int)ans.size(); ++ i) {
        if (real(ans[ i ]) < real(ans[ 0 ])) {
            swap(ans[ 0 ], ans[ i ]);
        }
        if (real(ans[ i ]) == real(ans[ 0 ]) && imag(ans[ i ]) < imag(ans[ 0 ])) {
            swap(ans[ 0 ], ans[ i ]);
        }
    }

    centru_obs = *ans.begin();
    sort(ans.begin() + 1, ans.end(), cmp);

    vector< pct > stk;
    int sz = 0;
    for (auto i : ans) {
        while (sz >= 2 && det(stk[sz - 2], stk[sz - 1], i) <= 0) {
            -- sz;
            stk.pop_back();
        }

        ++ sz;
        stk.push_back( i );
    }

    //for (auto i : stk)
      //  fout << i << "\n";
    return stk;
}

void citire () {
    int n;
    fin >> n;

    double px = INFINITY, py = INFINITY;
    for (int i = 1; i <= n; ++ i) {
        double x, y;
        fin >> x >> y;
        robot.push_back(pct(x, y));

        px = min(px, x);
        py = min(py, y);
    }

    fin >> m;
    for (int i = 1; i <= m; ++ i) {
        int nrp;
        fin >> nrp;

        vector< pct > obs_init;
        for (int j = 1; j <= nrp; ++ j) {
            double x, y;
            fin >> x >> y;
            obs_init.push_back(pct(x, y));
        }

        obs[ i ] = mareste( obs_init );
    }

    double dx, dy;
    fin >> dx >> dy;

    dx += real(robot[ 0 ]) - px;
    dy += imag(robot[ 0 ]) - py;
    destinatie = pct(dx, dy);
}

bool intersect (pct a, pct b, pct x, pct y) {
    if (cross(b - a, y - x) == 0) /// daca sunt paralele nu conteaza, chiar daca se intersecteaza
        return 0;

    return det(a, b, x) * det(a, b, y) < 0 && det(x, y, a) * det(x, y, b) < 0;
}

bool invalid (pct u) {
    for (int i = 1; i <= m; ++ i) {
        double ariet = 0, s = 0;
        bool marg = 0;

        for (int j = 0; j < (int)obs[ i ].size(); ++ j) {
            pct nxt = obs[ i ][ 0 ];
            if (j + 1 < (int)obs[ i ].size())
                nxt = obs[ i ][j + 1];

            ariet += cross(obs[ i ][ j ], nxt);

            double tr = fabs(det(obs[ i ][ j ], nxt, u));
            s += tr;

            if (tr == 0)
                marg = 1;
        }

        if (fabs(ariet) == s && marg == 0)
            return 1;
    }
    return 0;
}

void fa_graf () {
    cine[ 0 ] = robot[ 0 ];
    ++ nrnoduri;

    for (int i = 1; i <= m; ++ i) {
        for (auto j : obs[ i ]) {
            cine[ nrnoduri ++ ] = j;
        }
    }
    cine[ nrnoduri ++ ] = destinatie;

    for (int i = 0; i < nrnoduri; ++ i) {
        for (int j = i + 1; j < nrnoduri; ++ j) {
            bool ok = 1;

            for (int p = 1; p <= m && ok; ++ p) {
                for (int x = 0; x < (int)obs[ p ].size() && ok; ++ x) {
                    for (int y = x + 1; y < (int)obs[ p ].size() && ok; ++ y) {
                        if (intersect(cine[ i ], cine[ j ], obs[ p ][ x ], obs[ p ][ y ])) {
                            ok = 0;
                        }
                    }
                }
            }

            if (ok == 1 && !invalid(cine[ i ]) && !invalid(cine[ j ])) {
                double dist = sqrt(dot(cine[ i ] - cine[ j ], cine[ i ] - cine[ j ]));
                g[ i ].push_back(make_pair(j, dist));
                g[ j ].push_back(make_pair(i, dist));
            }
        }
    }
}

void extinde (Heap_node u) {
    for (auto i : g[ u.x ]) {
        if (d[ i.first ] > d[ u.x ] + i.second) {
            d[ i.first ] = d[ u.x ] + i.second;
            heap.push(Heap_node(i.first, d[ i.first ]));
        }
    }
}

void dijkstra () {
    for (int i = 0; i < pmax; ++ i) {
        d[ i ] = INFINITY;
    }

    d[ 0 ] = 0;
    heap.push(Heap_node(0, 0));

    while (!heap.empty()) {
        Heap_node u = heap.top();
        heap.pop();

        if (gata[ u.x ] == 1)
            continue;

        gata[ u.x ] = 1;
        extinde( u );
    }
}

int main () {
    citire ();
    fa_graf ();
    dijkstra ();

    if (d[nrnoduri - 1] == INFINITY) {
        fout << "-1\n";
    } else {
        fout << setprecision( 6 ) << fixed;
        fout << d[nrnoduri - 1] << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}