Cod sursa(job #2147717)

Utilizator Andrei_RAndrei Roceanu Andrei_R Data 28 februarie 2018 22:18:12
Problema Robot Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 8.12 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

const int nmax = 15, mmax = 30, pmax = 2505;
int N, M, NR[mmax], O[mmax], ariepoly[mmax];
double D[pmax];
struct punct { int x, y; } PI, PF, R[nmax], RD[nmax];
struct nod { int x, y, p; };
vector <punct> A[mmax], AUX, INF;
vector <nod> G;
vector < pair < int, double > > V[pmax];
queue <int> Q;
bitset <pmax> valid;

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

double absd (double a)
{
    if (a < 0) return -a;
    return a;
}

int semn (punct p1, punct p2, punct p3)
{
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

double arie (punct p1, punct p2, double x3, double y3)
{
    return absd ((p2.x - p1.x) * (y3 - p1.y) - (x3 - p1.x) * (p2.y - p1.y));
}

double dist (int x1, int y1, int x2, int y2)
{
    return sqrt ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool nuseintersecteaza (punct p1, punct p2, punct p3, punct p4)
{
    if (semn (p1, p2, p3) * semn (p1, p2, p4) >= 0)
        return 1;
    if (semn (p3, p4, p1) * semn (p3, p4, p2) >= 0)
        return 1;
    return 0;
}

void citire ()
{
    int i, j;
    punct p;

    scanf ("%d", &N);

    scanf ("%d%d", &R[1].x, &R[1].y);
    PI.x = R[1].x;
    PI.y = R[1].y;
    for (i = 2; i <= N; i++)
    {
        scanf ("%d%d", &R[i].x, &R[i].y);
        PI.x = min (PI.x, R[i].x);
        PI.y = min (PI.y, R[i].y);
    }

    scanf ("%d", &M);
    for (i = 1; i <= M; i++)
    {
        scanf ("%d", &NR[i]);
        O[i] = 0;
        for (j = 0; j < NR[i]; j++)
        {
            scanf ("%d%d", &p.x, &p.y);
            /*
            if (j > 0)
                if (A[i][O[i]].y > p.y || (A[i][O[i]].y == p.y && A[i][O[i]].x > p.x))
                    O[i] = j;
            */
            A[i].push_back (p);
        }
    }

    scanf ("%d%d", &PF.x, &PF.y);
}

void preprocesare ()
{
    R[0] = R[N];
    R[N+1] = R[1];

    for (int i = 1; i <= N; i++)
    {
        RD[i].x = R[i].x - PI.x;
        RD[i].y = R[i].y - PI.y;
    }
}

void construieste_start ()
{
    nod ng;
    ng.x = PI.x;
    ng.y = PI.y;
    ng.p = 0;
    G.push_back (ng);
}

void coliziuni (int n)
{
    //caut punctele care vor forma noul obstacol, adaptat la dimensiunile robotului
    int i, j;
    punct p;
    AUX.clear ();

    for (i = 0; i < NR[n]; i++)
    {
        for (j = 1; j <= N; j++)
        {
            p.x = A[n][i].x - RD[j].x;
            p.y = A[n][i].y - RD[j].y;

            AUX.push_back (p);
            if (AUX.front().y > AUX.back().y || (AUX.front().y == AUX.back().y && AUX.front().x > AUX.back().x))
            {
                swap (AUX.front(), AUX.back());
            }
        }
    }
}

void infasoara (int n)
{
    if (AUX.size() <= 1)
    {
        INF.push_back (AUX.front ());
        if (AUX.size () == 1)
            INF.push_back (AUX.back ());
        return;
    }

    int i, j;
    punct pmemo;
    vector <punct> :: iterator it;
    INF.clear ();

    pmemo = AUX.front();
    for (i = 0; i < AUX.size(); i++)
    {
        AUX[i].x -= pmemo.x;
        AUX[i].y -= pmemo.y;
    }

    it = AUX.begin(); it++;
    sort (it, AUX.end(), cmp);
    //AUX.pop_back (pzero);

    for (i = AUX.size() - 1; i > 1 && semn (AUX.front(), AUX[i], AUX[i-1]) == 0; i--);
    for (j = AUX.size() - 1; i < j; i++, j--) swap (AUX[i], AUX[j]);

    INF.push_back (AUX[0]);
    INF.push_back (AUX[1]);
    INF.push_back (AUX[2]);

    for (i = 3; i < AUX.size(); i++)
    {
        while (INF.size () > 1 && semn (INF[INF.size() - 2], INF.back(), AUX[i]) <= 0)
            INF.pop_back ();
        INF.push_back (AUX[i]);
    }

    for (i = 0; i < INF.size(); i++)
    {
        INF[i].x += pmemo.x;
        INF[i].y += pmemo.y;
    }
}

void reconstruieste (int n)
{
    nod ng;
    double c;
    int i, j;
    A[n].clear ();

    for (i = j = G.size(); !INF.empty (); j++)
    {
        ng.x = INF.back().x;
        ng.y = INF.back().y;
        ng.p = n;

        G.push_back (ng);
        A[n].push_back (INF.back ());
        INF.pop_back ();
    }
    j--;

    A[n].push_back (A[n].front());

    for (i = 2; i < A[n].size() - 1; i++)
    {
        ariepoly[n] += abs (semn (A[n].front(), A[n][i-1], A[n][i]));
    }
}

void construieste_finish ()
{
    int i, n, k, arie1;
    bool ok;
    nod ng;
    punct p1;

    ng.x = PF.x;
    ng.y = PF.y;
    ng.p = M + 1;
    G.push_back (ng);

    valid[0] = 1;
    for (i = 1; i < G.size(); i++)
    {
        ok = 1;
        p1.x = G[i].x;
        p1.y = G[i].y;

        for (n = 1; n <= M; n++)
        {
            if (G[i].p == n) continue;
            arie1 = 0;

            for (k = 1; k < A[n].size(); k++)
            {
                if (semn (p1, A[n][k-1], A[n][k]) == 0)
                {
                    arie1 = -1;
                    break;
                }
                arie1 += absd(semn (p1, A[n][k-1], A[n][k]));
            }

            if (arie1 == ariepoly[n])
            {
                ok = 0;
                break;
            }
        }
        valid[i] = ok;
    }
}

void fa_graf ()
{
    int i, j, n, k, k2, nrpoz, nrneg, arie1, arie2, arie3;
    double c, xm, ym, aried;
    punct p1, p2, p3, p4;
    bool ok, apartine_latura;

    construieste_start ();
    for (i = 1; i <= M; i++)
    {
        coliziuni (i);
        infasoara (i);
        reconstruieste (i);
    }
    construieste_finish ();

    for (i = 1; i < G.size(); i++)
    {
        if (valid[i] == 0) continue;
        p1.x = G[i].x;
        p1.y = G[i].y;

        for (j = 0; j < i; j++)
        {
            if (valid[j] == 0) continue;
            if (G[i].p == G[j].p)
                if ( !( (j == i - 1) || (G[j-1].p != G[j].p && G[i].p != G[i+1].p) ) )
                    continue;

            ok = 1;
            p2.x = G[j].x;
            p2.y = G[j].y;

            xm = (p1.x + p2.x) / 2.0;
            ym = (p1.y + p2.y) / 2.0;

            for (n = 1; n <= M && ok; n++)
            {
                /*
                aried = 0;
                apartine_latura = 0;
                */
                for (k = 1; k < A[n].size() && ok; k++)
                {
                    for (k2 = 1; k2 < k && ok; k2++)
                    {
                        p3 = A[n][k];
                        p4 = A[n][k2];

                        /*
                        aried += arie (p3, p4, xm, ym);
                        if (arie (p3, p4, xm, ym) == 0)
                            apartine_latura = 1;
                        */
                        ok &= nuseintersecteaza (p1, p2, p3, p4);
                    }
                }
                /*
                if (G[i].p != G[j].p && (int)(aried + 0.02) == ariepoly[n] && !apartine_latura)
                    ok = 0;
                */
            }
            if (ok == 0) continue;

            c = dist (p1.x, p1.y, p2.x, p2.y);
            V[i].push_back (make_pair (j, c));
            V[j].push_back (make_pair (i, c));
        }
    }
}

void bellman_ford ()
{
    int n, f, i;
    double c;

    Q.push (0);
    for (i = 0; i < G.size(); i++)
    {
        D[i] = -1;
    }
    D[0] = 0;

    while (!Q.empty())
    {
        n = Q.front ();
        Q.pop ();

        for (i = 0; i < V[n].size(); i++)
        {
            f = V[n][i].first;
            c = V[n][i].second;

            if (D[f] == -1 || D[f] > D[n] + c)
            {
                D[f] = D[n] + c;
                Q.push (f);
            }
        }
    }

    printf ("%.2lf\n", D[G.size() - 1]);
}

int main ()
{
    freopen ("robot.in", "r", stdin);
    freopen ("robot.out", "w", stdout);

    citire ();
    preprocesare ();
    fa_graf ();
    bellman_ford ();

    return 0;
}