Cod sursa(job #953054)

Utilizator primulDarie Sergiu primul Data 24 mai 2013 18:30:08
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.88 kb
#include <fstream>
#include <math.h>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("robot.in");
ofstream o("robot.out");
struct spct{int x; int y;};
struct nod{int v; double di; nod *next;};
nod *G[2601];
spct pol[26][2601],bot[11],tmp[2601],pct[2601];
int i,j,n,m,nr[26],tmp0,st[2601],util[2701];
int minx,miny,NR,skip[2601];
float dist[2601];
int add(int x,int y,double v)
{nod *nou=new nod;
nou->v=y;
nou->di=v;
nou->next=G[x];
G[x]=nou;
return 0;
}
int cmp(spct a,spct b)
{
if (a.y==b.y)
return (a.x<b.x);
else return (a.y<b.y);
}
inline int semn(spct x, spct y, spct z)
{
int A=x.y-y.y,B=y.x-x.x,C=x.x*y.y-y.x*x.y;
int tmp=A*z.x+B*z.y+C;
if (tmp<0) return -1;
if (tmp==0) return 0;
return 1;
}
int conv_hull(spct x[],int n)
{
sort(x,x+n+1,cmp);
int p=1,i=1;
st[0]=1;
st[1]=0;
for (i=0;i<=n;i++) util[i]=0;
for (i=1;i>=0;i+=p=(i==n?-p:p))
{
if (!util[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)
util[st[st[0]--]]=0;
util[st[++st[0]]=i]=1;
}
}
return 0;
}
int e_inside(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) || (k.x<=x[i].x && x[i+1].x<=k.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 intre(spct a, spct b, spct c)
{
if (a.x!=b.x)
return ((a.x<c.x && c.x<b.x) || (b.x<c.x && c.x<a.x));
else ((a.y<c.y && c.y<b.y) || (b.y<c.y && c.y<a.y));
return 0;
}
int intersect(spct a,spct b,spct c,spct d)
{
int abc,abd,cda,cdb;
abc=semn(a,b,c);
if (!abc && intre(a,b,c)) return 1;
abd=semn(a,b,d);
if (!abd && intre(a,b,d)) return 1;
cda=semn(c,d,a);
cdb=semn(c,d,b);
return ((abc*abd<0) && (cda*cdb<0));
}
int dijkstra()
{
int i,j,min;
for (i=1;i<=NR;i++) dist[i]=1000000000;
nod *nou=new nod;
for (i=0;i<=NR;i++) util[i]=0;
dist[0]=0;
i=0;
while (i!=NR)
{
util[i]=1;
for (nou=G[i];nou;nou=nou->next)
if (dist[nou->v]>dist[i]+nou->di)
dist[nou->v]=dist[i]+nou->di;
min=0;
while (dist[min]==0 || util[min]==1) min++;
for (j=1;j<=NR;j++)
if (!util[j] && dist[j]<dist[min])
min=j;
i=min;
}
return 0;
}
int nofitpolygon(int k)
{
tmp0=-1;
int i,j;
for (i=0;i<nr[k];i++)
for (j=0;j<n;j++)
{
tmp[++tmp0].x=pol[k][i].x+minx-bot[j].x;
tmp[tmp0].y=pol[k][i].y+miny-bot[j].y;
}
conv_hull(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];
return 0;
}
int main(void)
{
f>>n;
minx=11000;
miny=11000;
for (i=0;i<n;i++)
{f>>bot[i].x>>bot[i].y;
bot[i].x+=5000;
bot[i].y+=5000;
if (minx>bot[i].x) minx=bot[i].x;
if (miny>bot[i].y) miny=bot[i].y;
}
NR=0;
pct[0].x=minx;
pct[0].y=miny;
f>>m;
for (i=0;i<m;i++)
{
f>>nr[i];
for (j=0;j<nr[i];j++)
{
f>>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 (e_inside(pct[i],pol[j],nr[j])) skip[i]=1;
NR++;
f>>pct[NR].x>>pct[NR].y;
pct[NR].x+=5000;
pct[NR].y+=5000;
double val;
int ok,k,K,L;
for (i=0;i<=NR;i++)
{
if (!skip[i])
for (j=i+1;j<=NR;j++)
if (!skip[j])
{
ok=1;
for (k=0;k<m && ok;k++)
for (K=0;K<nr[k]-1 && ok;K++)
for (L=K+1;L<nr[k] && ok;L++)
if (intersect(pct[i],pct[j],pol[k][K],pol[k][L]))
ok=0;
if (ok)
{
val=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));
add(i,j,val);
add(j,i,val);
}
}
}
dijkstra();
o.setf(ios::fixed,ios::floatfield);
o.precision(3);
if (dist[NR]==1000000000)
o<<"-1\n";
else o<<dist[NR]<<"\n";
return 0;
}