Cod sursa(job #319368)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 31 mai 2009 16:50:05
Problema Robot Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.92 kb
#include <cstdio>     
#include <cmath>     
#include <algorithm>     
using namespace std;     
     
const int MAXN = 10;     
const int MAXM = 25;     
const int MAXP = 25 * 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;     
}