2678.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2678  User Id:fzk 
Memory:9556K  Time:703MS
Language:C++  Result:Accepted

Source 

#include"iostream.h"
#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( "%.3lf\n", dist[1] );
		else
			printf( "-1\n" );
	}

	return 0;
}