HDU 4617 立体几何-空间直线距离

题意：给出空间里n个圆的圆心，以及圆周上的两个点，（其实是个光柱的一个截面），问这个光柱的截面原有的圆柱间最近的距离。其实也就是问经过圆心o点方向向量为这个圆面的法向量的直线的距离减去两个圆的半径的最小值。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-8;
int sgn(double x)
{
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    else return 1;
}
struct point3D
{
    double x,y,z;
    point3D(double _x = 0,double _y = 0,double _z = 0)
    {
        x = _x;
        y = _y;
        z = _z;
    }
    point3D operator -(const point3D &b)const
    {
        return point3D(x-b.x,y-b.y,z-b.z);
    }
    point3D operator ^(const point3D &b)const
    {
        return point3D(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
    }
    double operator *(const point3D &b)const
    {
        return x*b.x+y*b.y+z*b.z;
    }
    void input()
    {
        scanf("%lf%lf%lf",&x,&y,&z);
    }
};
double Norm(point3D p)
{
    return sqrt(p*p);
}
double calc(point3D a,point3D k1,point3D b,point3D k2)//计算两条异面直线的距离,分别是一点，方向向量。
{
    point3D tmp = k1^k2;
    return fabs(tmp*(a-b))/sqrt(tmp*tmp);
}
struct node
{
    point3D o,p1,p2,f;
    double d;
    void input()
    {
        o.input();
        p1.input();
        p2.input();
    }
    void get()
    {
        f=(p1-o)^(p2-o);
        d=Norm(o-p1);
    }
} data[50];
int t,n;
void solve()
{
    double m=1e30;
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
        {
            m=min(m,calc(data[i].o,data[i].f,data[j].o,data[j].f)-data[i].d-data[j].d);
            if(sgn(m)<=0)
            {
                puts("Lucky");
                return;
            }
        }
    printf("%.2f\n",m);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            data[i].input(),data[i].get();
        solve();
    }
    return 0;
}