题目大意：空间中有许多无限长的棒子（圆柱体），求棒子间最小距离。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 using namespace std; 6 7 const double eps = 1e-8; 8 struct Point3//三维空间点 9 { 10 double x, y, z; 11 Point3(double x=0,double y=0,double z=0): x(x),y(y),z(z){} 12 Point3 operator + (Point3 &t){return Point3(x+t.x, y+t.y, z+t.z);} 13 Point3 operator - (Point3 &t) {return Point3(x-t.x, y-t.y, z-t.z);} 14 Point3 operator * (double p) {return Point3(x*p, y*p, z*p);} 15 Point3 operator / (double p) {return Point3(x/p, y/p, z/p);} 16 }; 17 typedef Point3 Vector3; 18 struct Line//空间直线 19 { 20 Point3 a,b; 21 }; 22 int dcmp(double x) 23 { 24 if(fabs(x) < eps) return 0; 25 return x < 0 ? -1 : 1; 26 } 27 double Dot(Vector3 A,Vector3 B) { return A.x*B.x + A.y*B.y + A.z*B.z; } 28 double Length2(Vector3 A) { return Dot(A, A); } 29 Vector3 Cross(Vector3 A, Vector3 B) { return Vector3(A.y*B.z - A.z*B.y, A.z*B.x - A.x*B.z, A.x*B.y - A.y*B.x); } 30 inline double min(double a,double b) 31 { 32 if(dcmp(b-a)>=0) return a; 33 return b; 34 } 35 double LineToLine(Line u,Line v)//空间直线间距离 36 { 37 Vector3 t=Cross(u.a-u.b,v.a-v.b); 38 return fabs(Dot(u.a-v.a,t))/sqrt(Length2(t)); 39 } 40 41 Line L[35]; 42 double R[35]; 43 44 void init(int i) 45 { 46 Point3 a,b,c; 47 scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&a.z,&b.x,&b.y,&b.z,&c.x,&c.y,&c.z); 48 Vector3 n=Cross(b-a,c-a);//平面法向量 49 L[i].a=a;L[i].b=a+n;R[i]=sqrt(Length2(b-a)); 50 } 51 52 int main() 53 { 54 int T,i,j,n; 55 scanf("%d",&T); 56 while(T--) 57 { 58 scanf("%d",&n); 59 for(i=0;i<n;i++) init(i); 60 bool flag=0; 61 double ans=1e20; 62 for(i=0;i<n&&!flag;i++) 63 { 64 for(j=i+1;j<n&&!flag;j++) 65 { 66 double temp=LineToLine(L[i],L[j]); 67 if(dcmp(R[i]+R[j]-temp)>=0) 68 flag=1; 69 else ans=min(ans,temp-R[i]-R[j]); 70 } 71 } 72 if(flag) printf("Lucky "); 73 else printf("%.2lf ",ans); 74 } 75 return 0; 76 }