Cod sursa(job #843295)

Utilizator stoicatheoFlirk Navok stoicatheo Data 27 decembrie 2012 18:10:52
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.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;
}