Cod sursa(job #297620)

Utilizator katamashCatalin Tamas katamash Data 5 aprilie 2009 15:05:56
Problema Robot Scor 0
Compilator cpp Status done
Runda preONI Marime 12.3 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;   
}  
#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;
}