HDU 4741 Save Labman No.004 （几何）

题意：求空间两线的最短距离和最短线的交点

题解：

线性代数和空间几何，主要是用叉积，点积，几何。

知道两个方向向量s1，s2，求叉积可以得出他们的公共垂直向量，然后公共垂直向量gamma和两线上的点形成的向量做内积，

在除掉gamma的长度就得到投影，即是最短距离。

然后求两个点可以用gamma和s2的叉积和l2上的一个点描述一个平面，再求平面和线的交点，

把（p2-p1）*n 和（p0-p1）*n相除算出比例乘上p2-p1得到交点和p1的差，再加上p1就求出交点了

学习点：计算几何的一些东西

#include<cstdio>

#include<cmath>

inline double fun(double a, double b, double c, double d){

    return a*d - b*c;

}

#define squ(x) ((x)*(x))

struct Poi

{

    double x,y,z;

    Poi(double X = , double Y = , double Z = ){

        x = X; y = Y; z = Z;

    }

    void input(){

        scanf("%lf%lf%lf",&x,&y,&z);

    }

    Poi operator + (const Poi & rhs){

        return Poi(x+rhs.x,y+rhs.y,z+rhs.z);

    }

    Poi operator - (Poi & rhs){

        return Poi(x-rhs.x,y-rhs.y,z-rhs.z);

    }

    Poi operator ^(Poi & rhs){

        return Poi(fun(y,z,rhs.y,rhs.z),-fun(x,z,rhs.x,rhs.z),fun(x,y,rhs.x,rhs.y));

    }

    Poi operator *(double t){

        return Poi(x*t,y*t,z*t);

    }

    double operator *(const Poi & rhs){

        return x*rhs.x+y*rhs.y+z*rhs.z;

    }

};

typedef Poi Vector;

double Dot(const Vector & a,const Poi& b) {

     return a.x*b.x+a.y*b.y+a.z*b.z;

}

Poi LinePlaneIns(Poi &p1,Poi &p2,Poi &p0,Vector &n){

    Vector v = p2 - p1;

    double Ratio = (Dot(n,p0-p1))/(Dot(n,v));//保证相交

    return p1+v*Ratio;

}

double Length(const Vector &x){

    return sqrt(squ(x.x)+squ(x.y)+squ(x.z));

}

int main()

{

   // freopen("in.txt","r",stdin);

    int T;

    scanf("%d",&T);

    while(T--){

        Poi p1,p2,p3,p4;

        p1.input();

        p2.input();

        p3.input();

        p4.input();

        Vector alpha = p2 - p1;

        Vector beta = p4 - p3;

        Vector gamma = alpha^beta;

        double distance = fabs(Dot(gamma,(p1-p3))/Length(gamma));

        Vector n1 = alpha^gamma;

        Vector n2 = beta^gamma;

        Poi ins1 = LinePlaneIns(p1,p2,p3,n2);

        Poi ins2 = LinePlaneIns(p3,p4,p1,n1);

        printf("%.6lf\n%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf\n",distance,ins1.x,ins1.y,ins1.z,ins2.x,ins2.y,ins2.z);

    }

    return ;

}

巴特西

HDU 4741 Save Labman No.004 （几何）

最新文章

热门文章