Cod sursa(job #253241)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 16:31:17
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.48 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;  
 }