HDU 4617 Weapon 三维计算几何

题意：给你一些无限长的圆柱，知道圆柱轴心直线（根据他给的三个点确定的平面求法向量即可）与半径，判断是否有圆柱相交。如果没有，输出柱面最小距离。

一共只有30个圆柱，直接暴力一下就行。

判相交/相切：空间直线距离是否小于等于两圆柱半径和
若无相交，求最小：空间直线距离-两圆柱半径和

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 
  7 using namespace std;
  8 
  9 const double EPS = 1e-9;
 10 const int MAXN = 40;
 11 
 12 struct Point3  //空间点
 13 {
 14     double x, y, z;
 15 };
 16 
 17 struct Line3   //空间直线
 18 {
 19     Point3 a, b;
 20 };
 21 
 22 struct plane3   //空间平面
 23 {
 24     Point3 a, b, c;
 25     plane3(){}
 26     plane3( Point3 a, Point3 b, Point3 c ):
 27     a(a), b(b), c(c) { }
 28 };
 29 
 30 struct Cylinder
 31 {
 32     Point3 center;   //圆柱轴线经过的一点
 33     Point3 a, b;     //与中心点在同一平面的两点
 34     Line3 FaXian;    //轴线
 35     double R;        //圆柱半径
 36 };
 37 
 38 Cylinder CC[MAXN];
 39 
 40 Point3 Read_Point()
 41 {
 42     Point3 p;
 43     scanf("%lf%lf%lf", &p.x, &p.y, &p.z );
 44     return p;
 45 }
 46 
 47 double dcmp( double a )
 48 {
 49     if ( fabs( a ) < EPS ) return 0;
 50     return a < 0 ? -1 : 1;
 51 }
 52 
 53 //三维叉积
 54 Point3 Cross3( Point3 u, Point3 v )
 55 {
 56     Point3 ret;
 57     ret.x = u.y * v.z - v.y * u.z;
 58     ret.y = u.z * v.x - u.x * v.z;
 59     ret.z = u.x * v.y - u.y * v.x;
 60     return ret;
 61 }
 62 
 63 //三维点积
 64 double Dot3( Point3 u, Point3 v )
 65 {
 66     return u.x * v.x + u.y * v.y + u.z * v.z;
 67 }
 68 
 69 //矢量差
 70 Point3 Subt( Point3 u, Point3 v )
 71 {
 72     Point3 ret;
 73     ret.x = u.x - v.x;
 74     ret.y = u.y - v.y;
 75     ret.z = u.z - v.z;
 76     return ret;
 77 }
 78 
 79 //取平面法向量
 80 Point3 NormalVector( plane3 s )
 81 {
 82     return Cross3( Subt( s.a, s.b ), Subt( s.b, s.c ) );
 83 }
 84 Point3 NormalVector( Point3 a, Point3 b, Point3 c )
 85 {
 86     return Cross3( Subt( a, b ), Subt( b, c ) );
 87 }
 88 
 89 //两点距离
 90 double TwoPointDistance( Point3 p1, Point3 p2 )
 91 {
 92     return sqrt( (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y) + (p1.z - p2.z)*(p1.z - p2.z) );
 93 }
 94 
 95 //向量的模
 96 double VectorLenth( Point3 p )
 97 {
 98     return sqrt( p.x*p.x + p.y*p.y + p.z*p.z );
 99 }
100 
101 //空间直线距离
102 double LineToLine( Line3 u, Line3 v )
103 {
104     Point3 tmp = Cross3( Subt( u.a, u.b ), Subt( v.a, v.b ) );
105     return fabs( Dot3( Subt(u.a, v.a), tmp ) ) / VectorLenth(tmp);
106 }
107 
108 int N;
109 
110 int main()
111 {
112     int T;
113     scanf( "%d", &T );
114     while ( T-- )
115     {
116         scanf( "%d", &N );
117         for ( int i = 0; i < N; ++i )
118         {
119             CC[i].center = Read_Point();
120             CC[i].a = Read_Point();
121             CC[i].b = Read_Point();
122             CC[i].R = VectorLenth( Subt( CC[i].a, CC[i].center ) );
123             CC[i].FaXian.a = CC[i].center;
124             CC[i].FaXian.b = Subt( CC[i].center, NormalVector( CC[i].center, CC[i].a, CC[i].b ) );
125         }
126 
127         bool ok = true;
128         double MinAns = 1e200;
129         for ( int i = 0; ok && i < N; ++i )
130         for ( int j = i + 1; ok && j < N; ++j )
131         {
132             double tmp = LineToLine( CC[i].FaXian, CC[j].FaXian );
133             if ( dcmp( tmp - ( CC[i].R + CC[j].R ) ) <= 0 )
134             {
135                 ok = false;
136                 break;
137             }
138             MinAns = min( MinAns, tmp - ( CC[i].R + CC[j].R ) );
139         }
140 
141         if ( ok ) printf( "%.2f
", MinAns );
142         else puts("Lucky");
143     }
144     return 0;
145 }