Nu aveti permisiuni pentru a descarca fisierul grader_test55.in
Cod sursa(job #289314)
Utilizator | Data | 26 martie 2009 17:47:46 | |
---|---|---|---|
Problema | Robot | Scor | 100 |
Compilator | cpp | Status | done |
Runda | aa | Marime | 6.92 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;
}