Poj Solution 2678

http://poj.org/problem?id=2678

#include<iostream>
#include"stdio.h"
#include"math.h"
#include<vector>
#include<algorithm>
using namespace std;

const double eps=1e-8;
const int size = 1010;
////////////////////////////////
typedef double Type;/*????????*/
////////////////////////////////
struct point
{
    Type x,y;
    point(){x=y=0;}
    point(Type x,Type y):x(x),y(y){;}
    bool operator==(point &a){return x==a.x&&y==a.y;}
};
//????
inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}
inline Type dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
//??????????
double dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
struct line
{
    point a,b;
    line(){;}
    line(point &x,point &y):a(x),b(y){;}
};
point crosspoint(line l1,line l2)
{
    Type p1=cheng(l2.a,l1.a,l2.b),
         p2=cheng(l2.a,l2.b,l1.b);
    if(p1+p2==0)return l1.a;

    point c;
    c.x=(p1*l1.b.x+p2*l1.a.x)/(p1+p2);
    c.y=(p1*l1.b.y+p2*l1.a.y)/(p1+p2);
    return c;
}
int jiao(line l1,line l2)
{
    Type s1=cheng(l1.a,l1.b,l2.a),
    s2=cheng(l1.a,l1.b,l2.b),s3,s4;

    if((double)s1*s2>0)return 0;

    s3=cheng(l2.a,l2.b,l1.a);s4=cheng(l2.a,l2.b,l1.b);

    if((double)s3*s4>0)return 0;

    if((double)s1*s2<0&&(double)s3*s4<0)return 1;

    if( dcheng(l1.a,l2.a,l2.b)<=0
      ||dcheng(l1.b,l2.a,l2.b)<=0
      ||dcheng(l2.a,l1.a,l1.b)<=0
      ||dcheng(l2.b,l1.a,l1.b)<=0)
    return 2;

    return 0;

}
int in(point *p,int n,point judge)
{
    int c,j,k;point up,low,temp; 

    c=0;j=0;

    while(p[j].y==judge.y)j++;

    for(;j<n;j=k)
    { 
        k=j+1;

        while(p[k%n].y==judge.y&&p[k%n].x>judge.x) k++;

        up=p[j];
        low=p[k%n];

        if(up.y<low.y){    temp=up;up=low;low=temp; }

        if(up.y<judge.y||low.y>judge.y)continue;

        if(cheng(low,up,judge)<=0&&k==j+1)continue;

        c++;
    }

    if(c%2)return 1;
    else return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////
int in_line( point c, point a, point b )
{
    return cheng( c, a, b ) == 0 &&    dcheng( c, a, b ) < 0;
}
point ploy[310][310];
int n, pn[310], m;

point p[size];
double e[size][size];
int st[size], sn;
void init( )
{
    int i, j, k, l, k1, k2;
    bool key;
    line ln, ln2;
    point c, d;    
    for( i=0; i<size; i++ )
    for( j=0; j<size; j++ )
        e[i][j] = 1e100;
    scanf( "%d %lf %lf %lf %lf", &n, &p[0].x, &p[0].y, &p[1].x, &p[1].y ); 
    k = 2;
    for( i=0; i<n; i++ )
    {
        scanf( "%d", &pn[i] );
        for( j=0; j<pn[i]; j++ )
        {
            scanf( "%lf %lf", &ploy[i][j].x, &ploy[i][j].y );
            p[k++] = ploy[i][j];
        }
        ploy[i][j] = ploy[i][0];
    }
    m = k;    
    for( i=0; i<m; i++ )
    for( j=i+1; j<m; j++ )
    {
        ln.a = p[i];
        ln.b = p[j];
        key = true;

        for( k=0; k<n; k++ )
        {
            for( l=0; l<pn[k]; l++ )
                if( jiao( ln, line( ploy[k][l], ploy[k][l+1] ) ) == 1 )
                        break;
            if( l< pn[k] )
            {    key = false;    break; }
        }
        if( key )
        {
            for( l=0; l<m; l++ )
                if( in_line( p[l], p[i], p[j] ) )
                    break;
            if( l < m )
            {    key = false; }
        }
        if( key )
        {
            c.x = (p[i].x+p[j].x)/2;
            c.y = (p[i].y+p[j].y)/2;
            for( k=0; k<n; k++ )
            {
                for( l=0; l<pn[k]; l++ )
                    if( in_line( c, ploy[k][l], ploy[k][l+1]  ) )
                            break;
                if( l == pn[k] && in( ploy[k], pn[k], c ) )
                {    key = false;    break;    }
            }
        }

        if( key )
            e[i][j] = e[j][i] = dis( p[i], p[j] );
    }
    k = m;
    for( k1=0; k1<n; k1++ )
    for( k2=k1+1; k2<n; k2++ )
    {
        for( i=0; i<pn[k1]; i++ )
        {
            sn = 0;
            for( j=0; j<pn[k2]; j++ )
            {
                ln.a = ploy[k1][i];
                ln.b = ploy[k1][i+1];

                ln2.a = ploy[k2][j];
                ln2.b = ploy[k2][j+1];

                if( jiao( ln, ln2 ) == 1 )
                {
                    st[sn++] = k;
                    p[k++] = crosspoint( ln, ln2 );
                }
            }

            int a;
            st[sn] = st[0];
            for( a=0; a<sn; a++ )
                e[st[a]][st[a+1]] = e[st[a+1]][st[a]] = dis( p[st[a]], p[st[a+2]] );
        }
    }
    m = k;
    for( i=0; i<m; i++ )
    for( j=i+1; j<m; j++ )
        if( dis( p[i], p[j] ) < 1e-5 )
            e[i][j] = e[j][i] = 0;

}
double dist[size];
bool sign[size];
void dijstra()
{
    int i, j, k, n = ::m;
    double temp;
    for( i=1; i<n; i++ )
        dist[i] = 1e100;
    dist[0] = 0;
    memset( sign, 0, sizeof sign );
    for( i=0; i<n; i++ )
    {
        k = 1;
        for( j=0; j<n; j++ )
            if( !sign[j] && dist[k] > dist[j] )
                k = j;
        if( k == 1 )
            return ;

        sign[ k ] = true;

        for( j=0; j<n; j++ )
        {
            if( ( temp = dist[k] + e[k][j] ) < dist[j] )
                dist[j] = temp;
        }
    }

    return;
}
int main( )
{
    int cas;
    scanf( "%d", &cas );
    while( cas-- )
    {
        init( );
        dijstra( );

        if( dist[1] < 1e99 )
            printf( "%.3lfn", dist[1] );
        else
            printf( "-1n" );
    }

    return 0;
}