Cod sursa(job #2644730)

Utilizator AokijiAlex M Aokiji Data 25 august 2020 19:23:31
Problema Robot Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 8.37 kb
#include <fstream>
#include <iomanip>
#include <queue>
#include <algorithm>

using namespace std;

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

const int nmax = 500 + 10;
const int inf = (1 << 30);
const double eps = 1e-7;
bool gata[nmax + 1];
double d[nmax + 1];

struct pct{
    int x, y;

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

    inline bool operator < (const pct &a) const {
        if (x != a.x) return (x < a.x);
        return (y < a.y);
    }

    inline bool operator == (const pct &a) const {
        return (x == a.x && y == a.y);
    }
};

pct centru;
pct st[nmax + 1];

int m;
int incepe[nmax + 1], nrp[nmax + 1];
int unde[nmax + 1][nmax + 1];

vector< pct > eu, poli;
vector< pct > v;

vector< pair<pct, pct> > segm;

struct Heap{
    int x; double y;

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

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

inline bool cmp (pct a, pct b) {
    return (a.y - centru.y) * (b.x - centru.x) < (b.y - centru.y) * (a.x - centru.x);
}
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) );
}
inline long long arie (pct a, pct b, pct c) {
    return (1LL * a.x * b.y - 1LL * a.y * b.x) +
           (1LL * b.x * c.y - 1LL * b.y * c.x) +
           (1LL * c.x * a.y - 1LL * c.y * a.x);
}
inline int ccw (pct a, pct b, pct c) {
    long long A = arie(a, b, c);
    if (A == 0) return 0;
    if (A > 0) return 1;
    return -1;
}

inline void ecuatia_dreptei(pair<pct, pct> p, long long &a, long long &b, long long &c) {
    a = p.second.y - p.first.y;
    b = p.first.x - p.second.x;
    c = - a * p.first.x - b * p.first.y;
}

inline bool egal (double x, double y) {
    return (x - eps < y && y < x + eps);
}

inline bool apartine (double x, double y, pair<pct, pct> p, bool capete, pair<pct, pct> q) {
    if (p.first.y > p.second.y) {
        swap(p.first.y, p.second.y);
    }
    if (p.first.x > p.second.x) {
        swap(p.first.x, p.second.x);
    }

    if (capete == 0) {
        if (p.first.y + eps < y && y < p.second.y - eps &&
            p.first.x + eps < x && x < p.second.x - eps) { // in interiorul segmentului
            return 1;
        }
        if (p.first.y - eps < y && y < p.second.y + eps &&
                   p.first.x - eps < x && x < p.second.x + eps) { // este pe segment
            pct I = pct(x, y);
            bool ok1, ok2;
            ok1 = (I == p.first || I == p.second);
            ok2 = (I == q.first || I == q.second);
            return (!ok1 || !ok2); // dar nu este unul din capetele
                                // celuilalt segment
        }
        return 0;
    } else {
        return (p.first.y - eps < y && y < p.second.y + eps &&
                p.first.x - eps < x && x < p.second.x + eps);
    }
}

inline bool intersecteaza(pair<pct, pct> p, pair<pct, pct> q) {
    long long a1, b1, c1, a2, b2, c2;
    ecuatia_dreptei(p, a1, b1, c1);
    ecuatia_dreptei(q, a2, b2, c2);

    if (a1 * b2 == a2 * b1) return 0; /// sunt paralele

    long long da, db, dc;
    da = a1 - a2, db = b1 - b2, dc = c1 - c2;

    double x, y;
    y = 1.0 * (dc * a1 - da * c1) / (da * b1 - db * a1);
    if (a1 == 0) {
        x = (-y * b2 - 1.0 * c2) / a2;
    } else {
        x = (-y * b1 - 1.0 * c1) / a1;
    }

    //pct I = pct(x, y);

    return (apartine(x, y, p, 0, q) && apartine(x, y, q, 1, p));
}

void infasuratoare (int iind) {
    int ind = 0;
    for (int i = 1; i < (int)poli.size(); ++ i) {
        if (poli[ i ] < poli[ ind ]) {
            ind = i;
        }
    }
    swap(poli[ 0 ], poli[ ind ]);

    centru = poli[ 0 ];
    sort(poli.begin() + 1, poli.end(), cmp);

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

    nrp[ iind ] = top;
    incepe[ iind ] = (int)v.size();
    for (int i = 1; i <= top; ++ i) {
        unde[ (int)v.size() ][ iind ] = i;

        v.push_back( st[ i ] );
        segm.push_back( make_pair(st[ i ], st[i % top + 1]) );
    }
}

void proceseaza (int ind) {
    int cate = (int)poli.size();

    for (int i = 1; i < (int)eu.size(); ++ i) {
        int dx = eu[ i ].x - eu[ 0 ].x, dy = eu[ i ].y - eu[ 0 ].y;

        for (int j = 0; j < cate; ++ j) {
            poli.push_back(pct(poli[ j ].x - dx, poli[ j ].y - dy));
        }
    }

    infasuratoare( ind );
}

void precalc_unde () {
    for (int i = 0; i < (int)v.size(); ++ i) {
        for (int j = i + 1; j < (int)v.size(); ++ j) {
            if (v[ i ] == v[ j ]) {
                for (int p = 1; p <= m; ++ p) {
                    if (unde[ i ][ p ] == 0 && unde[ j ][ p ] == 0) continue;

                    if (unde[ i ][ p ] == 0) unde[ i ][ p ] = unde[ j ][ p ];
                    if (unde[ j ][ p ] == 0) unde[ j ][ p ] = unde[ i ][ p ];
                }
            }
        }
    }

    for (int i = 0; i < (int)v.size(); ++ i) {
        for (int j = 1; j <= m; ++ j) {
            int poz, neg, pe;
            poz = neg = pe = 0;

            for (int k = incepe[ j ]; k < incepe[ j ] + nrp[ j ] - 1; ++ k) {
                long long det = arie(v[ k ], v[k + 1], v[ i ]);

                if (det > 0) ++ poz;
                else if (det < 0) ++ neg;
                else pe = 1;

            }
            long long det = ccw(v[incepe[ j ] + nrp[ j ] - 1], v[ incepe[ j ] ], v[ i ]);
            if (det == 1) ++ poz;
            else if (det == -1) ++ neg;
            else pe = 1;

            if ((neg == 0 || poz == 0) && pe == 0) {
                gata[ i ] = 1;
                break;
            }
        }

    }
}

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

        if (x < pos.x) pos.x = x;
        if (y < pos.y) pos.y = y;
    }

    v.push_back( eu[ 0 ] );

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

        poli.clear();
        for (int j = 1; j <= cate; ++ j) {
            int x, y;
            fin >> x >> y;
            poli.push_back( pct(x, y) );
        }

        proceseaza( i );
    }

    int x, y;
    fin >> x >> y;

    v.push_back( pct(x + (eu[ 0 ].x - pos.x), y + (eu[ 0 ].y - pos.y)) );

    precalc_unde();
}

inline bool se_poate (int x, int y) {
    for (int pind = 1; pind <= m; ++ pind) {
        if (unde[ x ][ pind ] > 0 && unde[ y ][ pind ] > 0) {
            if (unde[ x ][ pind ] % nrp[ pind ] + 1 != unde[ y ][ pind ] &&
                unde[ y ][ pind ] % nrp[ pind ] + 1 != unde[ x ][ pind ]) {
                    return 0;
                }
        }
    }
    return 1;
}

void dijkstra() {
    int sf = (int)v.size() - 1;
    for (int i = 0; i <= sf; ++ i) {
        d[ i ] = INFINITY;
    }
    d[ 0 ] = 0;
    h.push(Heap(0, 0));

    while (!h.empty()) {
        Heap q = h.top();
        h.pop();

        if (gata[ q.x ] == 1) continue;
        if (q.x == sf) break;

        gata[ q.x ] = 1;

        for (int i = 1; i <= sf; ++ i) {
            if (gata[ i ] == 0 && se_poate(q.x, i)) {
                pair< pct, pct > drum = make_pair(v[ q.x ], v[ i ]);
                bool ok = 1;

                for (auto j : segm) {
                    if (intersecteaza(drum, j)) {
                        ok = 0;
                        break;
                    }
                }

                if (ok == 1) {
                    double cost = dist(v[ q.x ], v[ i ]);

                    if (d[ i ] > q.y + cost) {
                        d[ i ] = q.y + cost;
                        h.push(Heap(i, d[ i ]));
                    }
                }
            }
        }
    }
}

inline void afis() {
    fout << setprecision( 3 ) << fixed;
    fout << d[ (int)v.size() - 1 ] << "\n";
}

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

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