首页 > ACM题库 > HDU-杭电 > HDU 4741-Save Labman No.004-计算几何-[解题报告]HOJ
2015
09-17

HDU 4741-Save Labman No.004-计算几何-[解题报告]HOJ

Save Labman No.004

问题描述 :

Due to the preeminent research conducted by Dr. Kyouma, human beings have a breakthrough in the understanding of time and universe. According to the research, the universe in common sense is not the only one. Multi World Line is running simultaneously. In simplicity, let us use a straight line in three-dimensional coordinate system to indicate a single World Line.

During the research in World Line Alpha, the assistant of Dr. Kyouma, also the Labman No.004, Christina dies. Dr. Kyouma wants to save his assistant. Thus, he has to build a Time Tunnel to jump from World Line Alpha to World Line Beta in which Christina can be saved. More specifically, a Time Tunnel is a line connecting World Line Alpha and World Line Beta. In order to minimizing the risks, Dr. Kyouma wants you, Labman No.003 to build a Time Tunnel with shortest length.

输入:

The first line contains an integer T, indicating the number of test cases.

Each case contains only one line with 12 float numbers (x1, y1, z1), (x2, y2, z2), (x3, y3, z3), (x4, y4, z4), correspondingly indicating two points in World Line Alpha and World Line Beta. Note that a World Line is a three-dimensional line with infinite length.

Data satisfy T <= 10000, |x, y, z| <= 10,000.

输出:

The first line contains an integer T, indicating the number of test cases.

Each case contains only one line with 12 float numbers (x1, y1, z1), (x2, y2, z2), (x3, y3, z3), (x4, y4, z4), correspondingly indicating two points in World Line Alpha and World Line Beta. Note that a World Line is a three-dimensional line with infinite length.

Data satisfy T <= 10000, |x, y, z| <= 10,000.

样例输入:

1
1 0 1 0 1 1 0 0 0 1 1 1

样例输出:

0.408248
0.500000 0.500000 1.000000 0.666667 0.666667 0.666667

题目

求异面直线的间的最短距离,并且求出最短距离的线段在两直线上的点。比赛时,在网上找了个资料,需要解个二元一次的方程,估计自己写龊了,奇葩数据,总会出现误差。

后来重新找了个,在这

先求出两个点,直线1上的点应该是直线1和(直线2与1.2公垂线确定的平面的交点)

公垂线,以及平面,以及平面与直线的交点的做法参照那篇博客,或者回去看高数书,应该都行

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;

struct point
{
    double x,y,z;

    point(double _x,double _y,double _z)
        {
            x=_x;y=_y;z=_z;
        }
};

struct Vector  
{
    double x,y,z;
    Vector(double _x,double _y,double _z)
        {
            x=_x,y=_y,z=_z;
        }
};

struct plane    // ax+by+cz+d=0;
{
    double a,b,c,d;
    plane(double _a,double _b,double _c,double _d)
        {
            a=_a,b=_b,c=_c,d=_d;
        }
};

Vector getvector(point a,point b)//直线的方向向量
{
    Vector ans=Vector(a.x-b.x,a.y-b.y,a.z-b.z);
    return ans;
}

Vector Common_Vertical_Line(Vector a,Vector b)//公垂线的方向向量 a*b 
{
    Vector ans=Vector(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);
    return ans;
}

double pointDis(Vector a)//点距离
{
    return sqrt((a.x*a.x+a.y*a.y+a.z*a.z));
}

plane getPlane(Vector a,Vector b,point c) //求由一直线的方向向量a,与一直线的方向向量b,与a上的一点c确定的平面;
{
    Vector line=Common_Vertical_Line(a,b);
    plane ans=plane(line.x,line.y,line.z,line.x*(-1)*c.x+line.y*(-1)*c.y+line.z*(-1)*c.z);
    return ans;
}
point getPoint(plane P,Vector B,point C)//C是B所在直线上的一点,求B所在直线和平面P的交点
{
    double k=((-1)*P.b*C.y-P.a*C.x-P.c*C.z-P.d)/(P.a*B.x+P.b*B.y+P.c*B.z);
    point ans=point(B.x*k+C.x,B.y*k+C.y,B.z*k+C.z);
    return ans;
}


int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        double a,b,c;
        scanf("%lf%lf%lf",&a,&b,&c);point x1=point(a,b,c);
        scanf("%lf%lf%lf",&a,&b,&c);point y1=point(a,b,c);
        scanf("%lf%lf%lf",&a,&b,&c);point x2=point(a,b,c);
        scanf("%lf%lf%lf",&a,&b,&c);point y2=point(a,b,c);

        Vector  l1=getvector(x1,y1);
        Vector  l2=getvector(x2,y2);
        Vector line=Common_Vertical_Line(l1,l2);
        plane p1=getPlane(l1,line,x1);
        plane p2=getPlane(l2,line,x2);
        point ans2=getPoint(p1,l2,x2);
        point ans1=getPoint(p2,l1,x1);
        Vector ans=getvector(ans1,ans2);
        printf("%.6lf\n",pointDis(ans));
        printf("%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf\n",ans1.x,ans1.y,ans1.z,ans2.x,ans2.y,ans2.z);
    }
    return 0;
}

a(x1,y1,z1),b(x2,y2,z2);

            |  i    j   k   |

a*b=    |x1  y1  z1|  ={(y1*z2-z1*y2)i, (x2*z1-z2*x1)j, (x1*y2-y1*x2)k}

           |x2  y2  z2|

参考:http://blog.csdn.net/zhuhuangjian/article/details/11739851