POJ1556+线段相交

/*
dij+两点间距离
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;

const int maxn = 205;//point number
const int maxm = 105;//line number
const double inf = 99999999;
const double eps = 1e-8;

struct POINT{
	double x,y;
	int f;
}S,T;

struct LINE{
	double x1,y1,x2,y2;
	int f;
};

int cnt_line,cnt_point;
POINT point[ maxn ];
LINE line[ maxm ];
double mat[ maxn ][ maxn ];

double dist( POINT a,POINT b ){
	double sum = (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
	return sqrt( sum );
}

 double xmult( POINT a,POINT b,POINT c ){
     return ( a.x-c.x )*( b.y-c.y )-( a.y-c.y )*( b.x-c.x );
 }
 
 bool inLine( LINE now,POINT p ){
     double minx,maxx,miny,maxy;
     minx=min( now.x1,now.x2 );
     maxx=max( now.x1,now.x2 );
     miny=min( now.y1,now.y2 );
     maxy=max( now.y1,now.y2 );
     if( p.x>=minx&&p.x<=maxx&&p.y>=miny&&p.y<=maxy )
         return true;
     else
         return false;
 }
 
bool Intersection( LINE one,LINE two ){
     double d1,d2,d3,d4;
     POINT t1,t2,t3,t4;
     t1.x = one.x1,t1.y = one.y1,t2.x = one.x2,t2.y = one.y2;
     t3.x = two.x1,t3.y = two.y1,t4.x = two.x2,t4.y = two.y2;
     d1=xmult( t3,t2,t1 );
     d2=xmult( t4,t2,t1 );
     d3=xmult( t1,t3,t4 );
     d4=xmult( t2,t3,t4 );
     if( d1*d2<0&&d3*d4<0 )
         return true;//相互跨过
     if( d1==0&&inLine( one,t3 )==true )
         return true;
     if( d2==0&&inLine( one,t4 )==true )
         return true;
     if( d3==0&&inLine( two,t1 )==true )
         return true;
     if( d4==0&&inLine( two,t2 )==true )
         return true;//分别表示某个点在一条直线上的情况
     return false;
 }

void init(){
	cnt_line = cnt_point = 0;
	for( int i=0;i<maxn;i++ ){
		for( int j=0;j<maxn;j++ ){
			mat[ i ][ j ] = inf;
		}
	}
}//init

void addline( double x1,double y1,double x2,double y2 ){
	line[ cnt_line ].x1=x1,line[ cnt_line ].y1=y1;
	line[ cnt_line ].x2=x2,line[ cnt_line ].y2=y2;
	cnt_line++;
}

void addpoint( double x,double y ){
	point[ cnt_point ].x = x;
	point[ cnt_point ].y = y;
	cnt_point++;
}

bool test( POINT a,POINT b ){
	LINE tt;
	tt.x1 = a.x,tt.y1 = a.y;
	tt.x2 = b.x,tt.y2 = b.y;
	//printf("a.flag:%d b.flag:%d\n",a.f,b.f);
	for( int i=0;i<cnt_line;i++ ){
		if( a.f!=line[ i ].f && b.f!=line[ i ].f && Intersection( tt,line[ i ] )==1 )
			return false;
	}
	return true;
}

double dij( int s,int t ){
	int vis[ maxn ];
	double dis[ maxn ];
	for( int i=0;i<cnt_point;i++ ){
		dis[ i ] = mat[ s ][ i ];
		vis[ i ] = 0;
	}
	dis[ s ] = 0;
	vis[ s ] = 1;
	//double sum = 0;
	for( int i=0;i<cnt_point;i++ ){
		int k;
		double tmax;
		k =-1,tmax = inf;
		for( int j=0;j<cnt_point;j++ ){
			if( vis[ j ]==0&&tmax>dis[ j ] ){
				tmax = dis[ j ];
				k=j;
			}
		}
		if( k==-1 ) break;
		vis[ k ] = 1;
		//sum += tmax;
		for( int j=0;j<cnt_point;j++ ){
			if( vis[ j ]==0&&dis[ j ]>dis[ k ]+mat[ k ][ j ] ){
				dis[ j ] = dis[ k ]+mat[ k ][ j ];
			}
		}
	}
	return dis[ t ];
}

int main(){
	int m;
	while( scanf("%d",&m),m!=-1 ){
		init();
		S.x = 0.0,S.y = 5.0;
		T.x = 10.0,T.y = 5.0;
		if( m==0 ){
			printf("%.2lf\n",dist( S,T ));
			continue;
		}
		int flag = 0;
		point[ cnt_point ].f = flag++;
		addpoint( S.x,S.y );
		point[ cnt_point ].f = flag++;
		addpoint( T.x,T.y );//start and end 
		double x,y1,y2,y3,y4;
		for( int num=1;num<=m;num++ ){
			scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);
			
			line[ cnt_line ].f = flag;
			addline( x,0.0,x,y1 );
			line[ cnt_line ].f = flag;
			addline( x,y2,x,y3 );
			line[ cnt_line ].f = flag;
			addline( x,y4,x,10.0 );//这三条线段归为一类
			
			point[ cnt_point ].f = flag;
			addpoint( x,y1 );
			point[ cnt_point ].f = flag;
			addpoint( x,y2 );
			point[ cnt_point ].f = flag;
			addpoint( x,y3 );
			point[ cnt_point ].f = flag;
			addpoint( x,y4 );//这四个点归为一类
			
			flag++;
		}
		//printf("flag:%d\ncnt_point:%d\ncnt_line:%d\n",flag,cnt_point,cnt_line);
		for( int i=0;i<cnt_point;i++ ){
			for( int j=i+1;j<cnt_point;j++ ){
				if( point[ i ].f!=point[ j ].f&&test( point[ i ],point[ j ] )==true ){
					mat[ i ][ j ] = mat[ j ][ i ] = dist( point[ i ],point[ j ] );
					//printf("mat[ %d ][ %d ] = %.2lf\n",i,j,mat[i][j]);
				}
			}
		}
		if( mat[ 0 ][ 1 ]!=inf ){
			printf("%.2lf\n",mat[ 0 ][ 1 ]);
			continue;
		}
		double ans = dij( 0,1 );
		printf("%.2lf\n",ans);
	}
	return 0;
}