Hdu 4617 Weapon (三维计算几何异面直线距离)

曾经终败给现在 2022-09-15 05:35 166阅读 0赞

2013多校联合集训第二场的一道题。

题意：给出一个无限长圆柱截面上的圆心和两点，求是否有圆柱相交，若不相交，则输出圆柱间最小距离。

思路：利用圆心和另外两点确定截面法向量，求异面直线距离。测试数据比较弱。

详解可参考：http://blog.csdn.net/freezhanacmore/article/details/9671967

#include <cstdio>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    const int N=35;
    const double INF=1e15;
    const double EPS=1e-7;
    
    struct point3
    {
        double x,y,z;
    
        point3(){}
        point3(double _x,double _y,double _z)
        {x=_x;y=_y;z=_z;}
    
        void Get ()
        {
    		scanf("%lf%lf%lf",&x,&y,&z);
    	}
    
        point3 operator+(point3 a)
        {
            return point3(x+a.x,y+a.y,z+a.z);
        }
    
        point3 operator-(point3 a)
        {
            return point3(x-a.x,y-a.y,z-a.z);
        }
    
        point3 operator*(point3 a)  //叉积
        {
            return point3(y*a.z-z*a.y,z*a.x-x*a.z,x*a.y-y*a.x);
        }
    
        point3 operator*(double t)
        {
            return point3(x*t,y*t,z*t);
        }
    
        double operator^(point3 a)   //点积
        {
            return x*a.x+y*a.y+z*a.z;
        }
    
        point3 operator/(double t)
        {
            return point3(x/t,y/t,z/t);
        }
    
        double len ()      //长度
        {
            return sqrt(x*x+y*y+z*z);
        }
    
        point3 adjust (double L)  //调整为L长
        {
            double t=len();
            L/=t;
            return point3(x*L,y*L,z*L);
        }
    
        void print ()
        {
            printf("%.10lf %.10lf %.10lf\n",x+EPS,y+EPS,z+EPS);
        }
    };
    
    struct Circle
    {
        point3 o, p1, p2;
    
        void Input ()
        {
            o.Get();p1.Get();p2.Get();
        }
    }data[N];
    
    int sgn (double x)
    {
        if (fabs(x) < EPS)return 0;
        return x>0?1:-1;
    }
    
    double lineToLine (point3 a,point3 b,point3 p,point3 q)  //异面直线间距离
    {//参数：直线上两点
        point3 v=(b-a)*(q-p);
        return fabs((a-p)^v)/v.len();
    }
    //两异面直线距离：两直线上的点的连线在其法向量上的投影
    double LineToLine (point3 p1,point3 k1,point3 p2,point3 k2)
    {//参数：直线上一点及其法向量
        point3 nV=k1*k2;
        return fabs(nV^(p1-p2))/nV.len();
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,n;
    	scanf("%d",&T);
    	while (T--)
    	{
    	    scanf("%d",&n);
    	    int i;
    	    for (i=0;i<n;i++)
                data[i].Input();
    
            bool flag = true;//true为不相交
            double nmin=INF;
            for (i=0;i<n && flag;i++)
                for (int j=i+1;j<n && flag;j++)
                {
                    Circle c1=data[i];
                    Circle c2=data[j];
                    double r1=(c1.p1-c1.o).len();
                    double r2=(c2.p1-c2.o).len();
                    point3 k1=(c1.p1-c1.o)*(c1.p2-c1.o); //向量//轴线的方向
                    point3 k2=(c2.p1-c2.o)*(c2.p2-c2.o);
    
                    double d=LineToLine(c1.o,k1,c2.o,k2);
                    if (d<r1+r2)
                    {
                        flag=false;
                        break;
                    }
                    nmin=min(nmin,d-r1-r2);
                }
            if (flag==false || sgn(nmin)<=0) printf("Lucky\n");
            else printf("%.2lf\n",nmin);
    	}
    	return 0;
    }