Cod sursa(job #300020)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 7 aprilie 2009 10:45:32
Problema Robot Scor 100
Compilator cpp Status done
Runda preONI Marime 6.7 kb
#include <cstdio>    
#include <cmath>    
#include <algorithm>    
using namespace std;    
    
const int MAXN = 10;    
const int MAXM = 25;    
const int MAXP = 250 * MAXN + 1;    
int n, m, i, j, k, K, L, posx, posy;    
int nr[MAXM], tmp0, NR;    
struct spct { int x, y; } rob[MAXN], pol[MAXM][MAXP], tmp[MAXP], pct[MAXP];    
int skip[MAXP];    
int st[MAXP], used[MAXP];    
float dst[MAXP];    
int par[MAXP];    
    
#define min(x, y) (x <= y ? x : y)    
#define max(x, y) (x >= y ? x : y)    
struct nod    
{    
    int x;    
    double k;    
    nod *next;    
};    
    
class LIST    
{    
    public:    
    nod *top;    
    void push_back(int x, double k)    
    {    
        nod *aux = new nod;    
        aux -> x = x;    
        aux -> k = k;    
        aux -> next = top;    
        top = aux;    
    }    
} con[MAXP];    
    
int semn(spct a, spct b, spct c)    
{    
    int A = a.y - b.y, B = b.x - a.x, C = a.x * b.y - b.x * a.y;    
    int tmp = A * c.x + B * c.y + C;    
    if (tmp < 0) return -1;    
    if (tmp == 0) return 0;    
    return 1;    
}    
    
int cmp(struct spct a, struct spct b)    
{    
    if (a.y == b.y)    
        return a.x < b.x;    
    else    
        return a.y < b.y;    
}    
    
void convexhull(spct x[], int n)    
{    
    sort(x, x + n + 1, cmp);    
    memset(used, 0, sizeof(used));    
    st[0] = 1; st[1] = 0;    
    int p = 1, i;    
    for (i = 1; i >= 0; i += p = (i == n ? -p : p))    
        if (!used[i] && (x[i - 1].x != x[i].x || x[i - 1].y != x[i].y))    
        {    
            while (st[0] >= 2 && semn(x[st[st[0] - 1]], x[st[st[0]]], x[i]) < 0)    
                used[ st[ st[0]-- ] ] = 0;    
            used[ st[ ++st[0] ] = i ] = 1;    
        }    
}    
    
void nofitpolygon(int K)    
{    
    int i, j;    
    tmp0 = -1;    
    for (i = 0; i < nr[K]; i++)    
        for (j = 0; j < n; j++)    
        {    
            tmp[++tmp0].x = pol[K][i].x + (posx - rob[j].x);    
            tmp[tmp0].y = pol[K][i].y + (posy - rob[j].y);    
        }    
    
    convexhull(tmp, tmp0);    
    
    pol[K][nr[K] = 0] = tmp[st[1]];    
    pct[++NR] = tmp[st[1]];    
    for (i = 2; i < st[0]; i++)    
    {    
        while (i + 1 <= st[0] && semn(pol[K][nr[K]], tmp[st[i]], tmp[st[i + 1]]) == 0) i++;    
        if (i >= st[0]) continue;    
        pol[K][++nr[K]] = tmp[st[i]];    
        pct[++NR] = tmp[st[i]];    
    }    
    pol[K][++nr[K]] = pol[K][0];    
}    
    
void dijkstra()    
{    
    int i, j, min;    
    nod *p;    
    for (i = 0; i <= NR; i++)    
        dst[i] = 1000000000;    
    memset(used, 0, sizeof(used));    
    dst[0] = 0;    
    i = 0;    
    while (i != NR)    
   {    
        used[i] = 1;    
        for (p = con[i].top; p; p = p -> next)    
        {    
            if (dst[p -> x] > dst[i] + p -> k)    
            {    
                dst[p -> x] = dst[i] + p -> k;    
                par[p -> x] = i;    
            }    
        }    
        min = 0;    
        while (dst[min] == 0 || used[min] == 1) min++;    
        for (j = 1; j <= NR; j++)    
            if (!used[j] && dst[j] < dst[min])    
                min = j;    
        i = min;    
    }    
}    
    
int inBetween(spct a, spct b, spct c)    
{    
    if (a.x != b.x)             /* not vertical */    
        return (((a.x < c.x) && (c.x < b.x))    
                || ((b.x < c.x) && (c.x < a.x)));    
    else    
        return (((a.y < c.y) && (c.y < b.y))    
                || ((b.y < c.y) && (c.y < a.y)));    
}    
    
int intersect(spct a, spct b, spct c, spct d)    
{    
    int a_abc, a_abd, a_cda, a_cdb;    
     
    a_abc = semn(a, b, c);    
    if ((a_abc == 0) && inBetween(a, b, c))    
        return 1;    
    a_abd = semn(a, b, d);    
    if ((a_abd == 0) && inBetween(a, b, d))    
        return 1;    
    a_cda = semn(c, d, a);    
    a_cdb = semn(c, d, b);    
    
    return (((a_abc * a_abd) < 0) && ((a_cda * a_cdb) < 0));    
}    
    
int isin(spct k, spct x[], int n)    
{    
    int i, c = 0;    
    for (i = 0; i < n; i++)    
        if (semn(x[i], x[i + 1], k) == 0 && ((x[i].x <= k.x && k.x <= x[i + 1].x) || (x[i].x >= k.x && k.x >= x[i + 1].x)))    
            return 0;    
    for (i = 0; i < n; i++)    
    {    
        if ((((x[i].y <= k.y) && (k.y < x[i + 1].y)) ||    
             ((x[i + 1].y <= k.y) && (k.y < x[i].y))) &&    
            (k.x < ((float)x[i + 1].x - x[i].x) * ((float)k.y - x[i].y) / ((float)x[i + 1].y - x[i].y) + x[i].x))    
            c = !c;    
    }    
    return c;    
}    
    
int main()    
{    
    freopen("robot.in", "rt", stdin);    
    freopen("robot.out", "wt", stdout);    
    scanf("%d", &n);    
    posx = posy = 2147000000;    
    for (i = 0; i < n; i++)    
    {    
        scanf("%d %d", &rob[i].x, &rob[i].y);    
        rob[i].x += 5000; rob[i].y += 5000;    
        if (rob[i].x < posx) posx = rob[i].x;    
        if (rob[i].y < posy) posy = rob[i].y;    
    }    
    NR = 0; pct[0].x = posx; pct[0].y = posy;    
    scanf("%d", &m);    
    for (i = 0; i < m; i++)    
    {    
        scanf("%d", &nr[i]);    
        for (j = 0; j < nr[i]; j++)    
        {    
            scanf("%d %d", &pol[i][j].x, &pol[i][j].y);    
            pol[i][j].x += 5000; pol[i][j].y += 5000;    
        }    
        nofitpolygon(i);    
    }    
    for (i = 1; i <= NR; i++)    
        for (j = 0; j < m && !skip[i]; j++)    
            if (isin(pct[i], pol[j], nr[j]))    
                skip[i] = 1;    
    NR++;    
    scanf("%d %d", &pct[NR].x, &pct[NR].y);    
    pct[NR].x += 5000; pct[NR].y += 5000;    
    double fx; int bol;    
    for (i = 0; i <= NR; i++)    
        if (!skip[i])    
        for (j = i + 1; j <= NR; j++)    
        if (!skip[j])    
        {    
            bol = 1;    
            for (k = 0; k < m && bol; k++)    
            for (K = 0; K < nr[k] - 1 && bol; K++)    
                for (L = K + 1; L < nr[k] && bol; L++)    
                    if (intersect(pct[i], pct[j], pol[k][K], pol[k][L]))    
                        bol = 0;    
            if (bol)    
            {    
                fx = sqrt((double)((pct[i].x - pct[j].x) * (pct[i].x - pct[j].x) + (pct[i].y - pct[j].y) * (pct[i].y - pct[j].y)));    
                con[i].push_back(j, fx);    
                con[j].push_back(i, fx);    
            }    
        }    
    dijkstra();    
    if (dst[NR] == 1000000000)    
        printf("-1\n");    
    else    
        printf("%.2f\n", dst[NR]);    
    return 0;    
}