Cod sursa(job #843289)

Utilizator stoicatheoFlirk Navok stoicatheo Data 27 decembrie 2012 18:07:11
Problema Robot Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.84 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;
}