Cod sursa(job #1898183)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 1 martie 2017 21:05:25
Problema Robot Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.66 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <iomanip>

using namespace std;

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

const int nmax = 500 + 5;
const int mmax = 25;
const int inf = (1 << 30);

bool gata[mmax + 5][nmax + 1];
double d[mmax + 5][nmax + 1];

struct pct {
    int x, y;

    inline bool operator == (const pct &a) const {
        return (x == a.x && y == a.y);
    }
} st[nmax + 1];

struct Heap {
    int pol, ind;
    double din;

    Heap() {}
    Heap (int _pol, int _ind, double _din) {
        pol = _pol, ind = _ind, din = _din;
    }

    inline bool operator < (const Heap &a) const {
        return (din > a.din);
    }
};
priority_queue< Heap > h;

int nrpoli;
pct start, dest;
pct centrusort;

vector< pct > robo;
vector< pct > aux, poli[mmax + 1];

inline bool cmp (pct a, pct b) {
    if (a.x == centrusort.x && b.x == centrusort.x) {
        return (a.y > b.y);
    }
    if (a.y == centrusort.y && b.y == centrusort.y) {
        return (a.x < b.x);
    }
    return (a.y - centrusort.y) * (b.x - centrusort.x) < (b.y - centrusort.y) * (a.x - centrusort.x);
}

inline int ccw (pct a, pct b, pct c) {
    int arie = (a.x * b.y - a.y * b.x)
             + (b.x * c.y - b.y * c.x)
             + (c.x * a.y - c.y * a.x);

    if (arie == 0) return 0;
    return ((arie < 0) ? -1 : 1);
}

void infasuratoare() {
    int bestpct = 0;
    for (int i = 1; i < (int)aux.size(); ++ i) {
        if (aux[ i ].x < aux[ bestpct ].x) {
            bestpct = i;
        } else if (aux[ i ].x == aux[ bestpct ].x && aux[ i ].y < aux[ bestpct ].x) {
            bestpct = i;
        }
    }
    swap(aux[ 0 ], aux[ bestpct ]);
    centrusort = aux[ 0 ];

    sort(aux.begin() + 1, aux.end(), cmp);
    int top = 0;
    st[ ++ top ] = aux[ 0 ];

    for (int i = 1; i < (int)aux.size(); ++ i) {
        while (top >= 2 && ccw(st[top - 1], st[ top ], aux[ i ]) != 1) {
            -- top;
        }
        st[ ++ top ] = aux[ i ];
    }

    aux.clear();
    for (int i = 1; i <= top; ++ i) {
        aux.push_back( st[ i ] );
    }
}

void transforma_poli (int ind) {
    aux.clear();
    for (int i = 0; i < (int)robo.size(); ++ i) {
        for (auto j : poli[ ind ]) {
            pct p = j;
            p.x -= robo[ i ].x - robo[ 0 ].x;
            p.y -= robo[ i ].y - robo[ 0 ].y;
            aux.push_back( p );
        }
    }

    infasuratoare();

    poli[ ind ].clear();
    for (auto i : aux) {
        poli[ ind ].push_back( i );
    }
}

inline double dist (pct a, pct b) {
    return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}

bool intersecteaza (pct a, pct b, pct x, pct y) {
    if (a == x || a == y) return 0;
    if (b == x || b == y) return 0;

    int xmic, xmare, ymic, ymare;
    xmic = max(min(a.x, b.x), min(x.x, y.x));
    xmare = min(max(a.x, b.x), max(x.x, y.x));
    ymic = max(min(a.y, b.y), min(x.y, y.y));
    ymare = min(max(a.y, b.y), max(x.y, y.y));

    if (xmic <= xmare && ymic <= ymare) {
        int ccw1 = ccw(a, b, x) * ccw(a, b, y);
        int ccw2 = ccw(x, y, a) * ccw(x, y, b);
        return (ccw1 == -1 && ccw2 == -1);
    }
    return 0;
}

bool verif (pct a, pct b) {
    for (int i = 1; i <= nrpoli; ++ i) {
        for (int j = 0; j < (int)poli[ i ].size(); ++ j) {
            for (int k = j + 1; k < (int)poli[ i ].size(); ++ k) {
                if (intersecteaza(a, b, poli[ i ][ j ], poli[ i ][ k ])) {
                    return 0;
                }
            }
        }
    }
    return 1;
}

void baga_ac_pol (int dir, Heap k) {
    int sz = (int)poli[ k.pol ].size();
    int nxt = (k.ind + dir + sz) % sz;
    double dst = dist(poli[ k.pol ][ k.ind ], poli[ k.pol ][ nxt ]);

    if (!verif(poli[ k.pol ][ k.ind ], poli[ k.pol ][ nxt ])) return ;

    if (gata[ k.pol ][ nxt ] == 0 && d[ k.pol ][ nxt ] > d[ k.pol ][ k.ind ] + dst) {
        d[ k.pol ][ nxt ] = d[ k.pol ][ k.ind ] + dst;
        h.push( Heap(k.pol, nxt, d[ k.pol ][ nxt ]) );
    }
}

void extinde (Heap k) {
    baga_ac_pol(1, k);
    baga_ac_pol(-1, k);

    pct acum = poli[ k.pol ][ k.ind ];

    for (int i = 0; i <= nrpoli + 1; ++ i) {
        if (i == k.pol) continue;

        for (int j = 0; j < (int)poli[ i ].size(); ++ j) {
            if (gata[ i ][ j ] == 1) continue;

            if (!verif(acum, poli[ i ][ j ])) continue;

            double dst = dist(acum, poli[ i ][ j ]);
            if (d[ i ][ j ] > d[ k.pol ][ k.ind ] + dst) {
                d[ i ][ j ] = d[ k.pol ][ k.ind ] + dst;
                h.push( Heap(i, j, d[ i ][ j ]) );
            }
        }
    }
}

void dijkstra() {
    for (int i = 0; i <= nrpoli + 1; ++ i) {
        for (int j = 0; j < (int)poli[ i ].size(); ++ j) {
            d[ i ][ j ] = INFINITY;
        }
    }

    d[ 0 ][ 0 ] = 0;
    h.push( Heap(0, 0, 0) );

    while (!h.empty() && gata[nrpoli + 1][ 0 ] == 0) {
        Heap k = h.top(); h.pop();

        if (gata[ k.pol ][ k.ind ] == 1) continue;

        gata[ k.pol ][ k.ind ] = 1;

        extinde( k );
    }
}

void posibil() {
    for (int i = 0; i <= nrpoli + 1; ++ i) {
        for (int j = 0; j < (int)poli[ i ].size(); ++ j) {
            bool ok = 1;

            for (int k = 0; k <= nrpoli + 1; ++ k) {
                bool in_int = 1;

                int dim = (int)poli[ k ].size();
                for (int shp = 0; shp < dim; ++ shp) {
                    if (ccw(poli[ k ][ shp ], poli[ k ][(shp + 1) % dim], poli[ i ][ j ]) != -1) {
                        in_int = 0;
                    }
                }

                if (in_int == 1) {
                    ok = 0; break;
                }
            }

            if (ok == 0) {
                gata[ i ][ j ] = 1;
            }
        }
    }
}

int main() {
    int n;
    fin >> n;

    pct pos;
    pos.x = inf, pos.y = inf;
    for (int i = 1; i <= n; ++ i) {
        pct p;
        fin >> p.x >> p.y;
        robo.push_back( p );

        pos.x = min(pos.x, p.x);
        pos.y = min(pos.y, p.y);
    }
    start = robo[ 0 ];

    fin >> nrpoli;
    for (int i = 1; i <= nrpoli; ++ i) {
        int nrpctpoli;
        fin >> nrpctpoli;
        for (int j = 1; j <= nrpctpoli; ++ j) {
            pct p;
            fin >> p.x >> p.y;
            poli[ i ].push_back( p );
        }

        transforma_poli( i );
    }

    fin >> dest.x >> dest.y;
    dest.x += start.x - pos.x;
    dest.y += start.y - pos.y;

    for (auto i : robo) {
        poli[ 0 ].push_back( i );
    }
    poli[nrpoli + 1].push_back( dest );

    posibil();
    dijkstra();

    double ans = d[nrpoli + 1][ 0 ];
    if (ans == INFINITY) {
        fout << -1 << "\n";
    } else {
        fout << setprecision( 5 ) << fixed;
        fout << ans << "\n";
    }

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