Weapon
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 266 Accepted Submission(s): 208
Problem Description
Doctor D. are researching for a horrific weapon. The muzzle of the weapon is a circle. When it fires, rays form a cylinder that runs through the circle verticality in both side. If one cylinder of rays touch another, there will be an horrific explosion. Originally, all circles can rotate easily. But for some unknown reasons they can not rotate any more. If these weapon can also make an explosion, then Doctor D. is lucky that he can also test the power of the weapon. If not, he would try to make an explosion by other means. One way is to find a medium to connect two cylinder. But he need to know the minimum length of medium he will prepare. When the medium connect the surface of the two cylinder, it may make an explosion.
Input
The first line contains an integer T, indicating the number of testcases. For each testcase, the first line contains one integer N(1 < N < 30), the number of weapons. Each of the next 3N lines  contains three float numbers. Every 3 lines represent one weapon. The first line represents the coordinates of center of the circle, and the second line and the third line represent two points in the circle which surrounds the center. It is supposed that these three points are not in one straight line. All float numbers are between -1000000 to 1000000.
Output
For each testcase, if there are two cylinder can touch each other, then output 'Lucky', otherwise output then minimum distance of any two cylinders, rounded to two decimals, where distance of two cylinders is the minimum distance of any two point in the surface of two cylinders.
Sample Input
3
3
0 0 0
1 0 0
0 0 1
5 2 2
5 3 2
5 2 3
10 22 -2
11 22 -1
11 22 -3
3
0 0 0
1 0 1.5
1 0 -1.5
112 115 109
114 112 110
109 114 111
-110 -121 -130
-115 -129 -140
-104 -114 -119.801961
3
0 0 0
1 0 1.5
1 0 -1.5
112 115 109
114 112 110
109 114 111
-110 -121 -130
-120 -137 -150
-98 -107 -109.603922
Sample Output
Lucky
2.32
Lucky
Source
2013 Multi-University Training Contest 2
Recommend
zhuyuanchen520
算法：
題目意思：
D博士發明了一個新武器，要對它進行威力測試。可以威力測試的條件是圓形炮筒兩端發出的射線構成無限長的圓柱，若有兩個圓柱相交後相切，則可以測試，輸出“Lucky”否則輸出圓柱間的最短距離。
算法思想：
計算幾何問題，將圓柱的中軸線為參考線，利用空間兩條直線的距離公式
|AB*n|/|n|,AB代表兩條中軸線的兩點構成的向量，這裡是兩個圓的圓心連線形成的向量。
n代表法線向量，即公垂線所在的向量。n向量可以通過兩圓的垂線的叉積得到。
AB*n為AB與n的內積。
代碼：
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
struct node
{
double x,y,z;
double a_x,a_y,a_z;
double b_x,b_y,b_z;
double n_x,n_y,n_z;
double r;
} Cir[40];
double fa_x,fa_y,fa_z,AB_x,AB_y,AB_z;
const double MAX=1e9;
double getDist(node A,node B)
{
double len_fa,len_she;
//法向量
fa_x=A.n_y*B.n_z-A.n_z*B.n_y;
fa_y=-A.n_x*B.n_z+A.n_z*B.n_x;
fa_z=A.n_x*B.n_y-A.n_y*B.n_x;
len_fa=sqrt(fa_x*fa_x+fa_y*fa_y+fa_z*fa_z);
//AB向量
AB_x=A.x-B.x;
AB_y=A.y-B.y;
AB_z=A.z-B.z;
len_she=fabs(AB_x*fa_x+AB_y*fa_y+AB_z*fa_z);
return len_she/len_fa;
}
int main()
{
int t,n,i;
cin>>t;
while(t--)
{
cin>>n;
for(i=0;i<n;++i)
{
cin>>Cir[i].x>>Cir[i].y>>Cir[i].z;
cin>>Cir[i].a_x>>Cir[i].a_y>>Cir[i].a_z;
cin>>Cir[i].b_x>>Cir[i].b_y>>Cir[i].b_z;
Cir[i].n_x=(Cir[i].a_y-Cir[i].y)*(Cir[i].b_z-Cir[i].z)-(Cir[i].a_z-Cir[i].z)*(Cir[i].b_y-Cir[i].y);
Cir[i].n_y=-(Cir[i].a_x-Cir[i].x)*(Cir[i].b_z-Cir[i].z)+(Cir[i].a_z-Cir[i].z)*(Cir[i].b_x-Cir[i].x);
Cir[i].n_z=(Cir[i].a_x-Cir[i].x)*(Cir[i].b_y-Cir[i].y)-(Cir[i].a_y-Cir[i].y)*(Cir[i].b_x-Cir[i].x);
//計算圓柱的半徑
Cir[i].r=sqrt((Cir[i].x-Cir[i].a_x)*(Cir[i].x-Cir[i].a_x)+(Cir[i].y-Cir[i].a_y)*(Cir[i].y-Cir[i].a_y)+(Cir[i].z-Cir[i].a_z)*(Cir[i].z-Cir[i].a_z));
}
int flag=1,j;
double dist,ans=MAX;
//遍歷
for(i=0;i<n-1 && flag;++i)
{
for(j=i+1;j<n;++j)
{
dist=getDist(Cir[i],Cir[j]);//計算兩個圓柱的距離
//cout<<dist-(Cir[i].r+Cir[j].r)<<endl;
ans=min(dist-(Cir[i].r+Cir[j].r),ans);
if(ans<=0)
{
flag=0;
break;
}
}
}
if(flag)
{
printf("%.2lf\n",ans);
}
else
{
cout<<"Lucky"<<endl;
}
}
return 0;
}
