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;
}
