题目意思 就是说 有一个起点一个终点 和一些虫洞，从一个虫洞进去然后出来，是不需要消耗时间的，注意点就是，虫洞是一条线段，你可以从线段的任意位置进去，从任意位置出来； 所以从一个虫洞到另一个虫洞的距离变成了空间的直线距离；
线段到线段的最短距离 用三分的方法
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cmath>
#define eps 1e-10
#define inf 0x1f1f1f1f
using namespace std; int dcmp( double a ){ if( abs(a) < eps ) return ; if(a > ) return ;return -;}
struct point{
double x,y,z;
point(){}
point( double x,double y,double z ):x(x),y(y),z(z){}
};
typedef point Vector ;
point operator + ( point a,point b ){
return point( a.x+b.x , a.y+b.y , a.z+b.z );
}
point operator - ( point a,point b ){
return point( a.x-b.x , a.y-b.y, a.z-b.z );
}
point operator * ( point a,double p ){
return point( a.x*p , a.y*p , a.z*p );
}
point operator / ( point a,double p ){
return point( a.x/p , a.y/p , a.z/p );
}
bool operator == ( point a,point b ){
if( dcmp(a.x-b.x) == && dcmp(a.y-b.y) == && dcmp(a.z-b.z) == )return ;
return ;
}
double Dot( point a,point b ){ return a.x*b.x + a.y*b.y + a.z*b.z; }
double Length( point a ){ return sqrt(Dot(a,a));}
double Angle( point a,point b ){ return acos(Dot(a,b))/Length(a)/Length(b); }
// 点到 平面p0 - n 的距离；n 必须为单位向量 n 是平面法向量
double p_po_n( const point &p,const point &po,const point n ){
return abs(Dot( p-po,n ));
}
// 点在 平面p0 - n 的投影 ； n 必须为单位向量 n 是平面法向量
point p_po_n_jec( const point &p,const point &p0,const point &n ){
return p-n*Dot( p-p0,n );
}
// 直线p1 p2 在平面 p0 - n 的交点，假设交点存在；唯一
point p_p_p( point p1,point p2,point p0,point n ){
point v = p2 - p1;
double t = ( Dot(n,p0-p1)/Dot(n,p2-p1) );
return p1 + v*t;
}
point cross( point a,point b ){
return point( a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z,a.x*b.y - a.y*b.x );
}
double area( point a,point b,point c ){ return Length(cross(b-a,c-a)); }
double dis_to_line( point p, point a,point b ){
point v1 = b-a, v2 = p-a;
return Length( cross(v1,v2)/Length(v1) );
}
// p 到 ab 线段的距离
double dis_to_segm( point p,point a,point b ){
if( a == b )return Length(p-a);
point v1 = b-a, v2 = p-a, v3 = p-b;
if( dcmp( Dot(v1,v2) ) < ) return Length(v2);
else if( dcmp( Dot(v1,v3) ) > ) return Length(v3);
else return Length(cross(v1,v2))/Length(v1);
}
// 四面体的体积
double volume( point a,point b,point c,point d ){
return Dot( d-a,cross(b-a,c-a) );
}
// 线段到线段的距离
double dis_l_to_l( point a,point b,point lt,point rt )
{
while( abs(rt.x - lt.x) > eps || abs(rt.y - lt.y) > eps || abs( rt.z - lt.z) > eps )
{
point temp; temp = lt + ( rt - lt )/3.0;
point now; now = lt + ( rt - lt )/3.0*2.0;
if( dis_to_segm(temp,a,b) < dis_to_segm(now,a,b) )
rt = now;
else lt = temp;
}
return dis_to_segm( rt,a,b );
}
point A[],B[];
double map[][];
double dis[]; int que[];bool vis[];
void spfa( int N )
{
int tail,hed; tail = hed = ;
for( int i = ; i < ; i++ )dis[i] = (<<);
memset( vis,,sizeof(vis) );
dis[] = ; que[tail++] = ; vis[] = true;
while( tail > hed )
{
int temp = que[hed++]; vis[temp] = false;
for( int i = ; i <= N; i++ )
if( dis[temp] + map[temp][i] < dis[i] )
{
dis[i] = dis[temp] + map[temp][i];
if( !vis[i] )
{
que[tail++] = i;
vis[i] = true;
}
}
}
}
int main( )
{
int T,N; scanf("%d",&T);
while( T-- )
{
scanf("%d",&N);
scanf("%lf%lf%lf",&A[].x,&A[].y,&A[].z);
scanf("%lf%lf%lf",&A[N+].x,&A[N+].y,&A[N+].z);
for( int i = ; i <= N; i++ )
{
scanf("%lf%lf%lf",&A[i].x,&A[i].y,&A[i].z);
scanf("%lf%lf%lf",&B[i].x,&B[i].y,&B[i].z);
}
for( int i = ; i <= N+; i++ )
for( int j = ; j <= N+; j++ )
map[i][j] = (<<);
map[][N+] = map[N+][] = Length( A[]-A[N+] );
for( int i = ; i <= N; i++ ){
map[i][] = map[][i] = dis_to_segm( A[],A[i],B[i] );
map[i][N+] = map[N+][i] = dis_to_segm( A[N+],A[i],B[i] );
}
for( int i = ; i <= N; i++ )
for( int j = i+; j <= N; j++ ){
map[i][j] = dis_l_to_l( A[i],B[i],A[j],B[j] );
map[j][i] = map[i][j];
}
spfa( N + );
printf("%.15lf\n",dis[N+]);
}
return ;
}