hdu 4741 Save Labman No.004（計算幾何）

Save Labman No.004

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 875    Accepted Submission(s): 259

Problem Description 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.  

Input 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.  

Output For each test case, please print two lines.

The first line contains one float number, indicating the length of best Time Tunnel. 

The second line contains 6 float numbers (xa, ya, za), (xb, yb, zb), seperated by blank, correspondingly indicating the endpoints of the best Time Tunnel in World Line Alpha and World Line Beta. 

All the output float number should be round to 6 digits after decimal point. Test cases guarantee the uniqueness of the best Time Tunnel.  

Sample Input

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

Sample Output

0.408248
0.500000 0.500000 1.000000 0.666667 0.666667 0.666667
        

Source 2013 ACM/ICPC Asia Regional Hangzhou Online  

Recommend liuyiding

題意：求異面直線的公垂線長度和2個垂足的坐标（保證2直線異面）

題解：明顯是模闆題....但是我沒有模闆....好吧，現在補上這個模闆....

#include<stdio.h>
#include<math.h>
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
using namespace std;
struct point3{
    double x,y,z;
    point3(){}
    point3(double _a,double _b,double _c):x(_a),y(_b),z(_c){};
    point3 operator + (point3 &temp)
    {
        return point3(x+temp.x,y+temp.y,z+temp.z);
    }
};
struct line3{point3 a,b;}A,B;
struct plane3{
    point3 a,b,c;
    plane3(){}
    plane3(point3 _a,point3 _b,point3 _c):a(_a),b(_b),c(_c){};
};
point3 xmult(point3 u,point3 v)
{
    point3 ret;
    ret.x=u.y*v.z-u.z*v.y;
    ret.y=u.z*v.x-u.x*v.z;
    ret.z=u.x*v.y-u.y*v.x;
    return ret;
}
double dmult(point3 u,point3 v)
{
    return u.x*v.x+u.y*v.y+u.z*v.z;
}
point3 subt(point3 u,point3 v)
{
    point3 ret;
    ret.x=u.x-v.x;
    ret.y=u.y-v.y;
    ret.z=u.z-v.z;
    return ret;
}
double vlen(point3 p)
{
    return sqrt(p.x*p.x+p.y*p.y+p.z*p.z);
}
point3 pvec(plane3 s)
{
    return xmult(subt(s.a,s.b),subt(s.b,s.c));
}
double linetoline(line3 u,line3 v,point3 &temp)
{
    temp=xmult(subt(u.a,u.b),subt(v.a,v.b));
    return fabs(dmult(subt(u.a,v.a),temp))/vlen(temp);
}
point3 intersection(line3 l,plane3 s)
{
    point3 ret=pvec(s);
    double t=(ret.x*(s.a.x-l.a.x)+ret.y*(s.a.y-l.a.y)+ret.z*(s.a.z-l.a.z))/
             (ret.x*(l.b.x-l.a.x)+ret.y*(l.b.y-l.a.y)+ret.z*(l.b.z-l.a.z));
    ret.x=l.a.x+(l.b.x-l.a.x)*t;
    ret.y=l.a.y+(l.b.y-l.a.y)*t;
    ret.z=l.a.z+(l.b.z-l.a.z)*t;
    return ret;
}
void solve()
{
    point3 normal;
    double dis=linetoline(A,B,normal);
    printf("%.6lf\n",dis);
    plane3 pla;
    pla=plane3(A.a,A.b,A.a+normal);
    point3 u=intersection(B,pla);
    pla=plane3(B.a,B.b,B.a+normal);
    point3 v=intersection(A,pla);
    printf("%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf\n",v.x,v.y,v.z,u.x,u.y,u.z);
}
int main()
{
    int t;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf",&A.a.x,&A.a.y,&A.a.z);
        scanf("%lf%lf%lf",&A.b.x,&A.b.y,&A.b.z);
        scanf("%lf%lf%lf",&B.a.x,&B.a.y,&B.a.z);
        scanf("%lf%lf%lf",&B.b.x,&B.b.y,&B.b.z);
        solve();
    }

    return 0;
}