[HDU 4741]Save Labman No.004[计算几何][精度]

题意:

求两条空间直线的距离,以及对应那条距离线段的两端点坐标.

思路:

有一个参数方程算最短距离的公式, 代入求即可.

但是这题卡精度... 用另外的公式(先算出a直线上到b最近的点p的坐标, 再算出b直线上到a最近的点q的坐标, 再求这两点距离)用double可以过, 直接参数方程的公式用long double才可以><而且下来交的时候..C++->WA,G++->AC...

long double

#include<cstdio>#include<cstring>#include<cmath>using namespace std;#define eps 1e-9struct point{long double x,y,z;double q,w,e;void read(){scanf("%lf%lf%lf",&q,&w,&e);x = q, y = w, z = e;}};point s1,s2,s3,s4;point ansp,ansq;long double ans;inline long double srt(long double x){return x*x;}long double dis(point a,point b){return sqrt(srt(a.x-b.x)+srt(a.y-b.y)+srt(a.z-b.z));};int main(){int nc;scanf("%d",&nc);while(nc--){s1.read();s2.read();s3.read();s4.read();long double a1=srt(s1.x-s2.x)+srt(s1.y-s2.y)+srt(s1.z-s2.z);long double b1=-((s2.x-s1.x)*(s4.x-s3.x)+(s2.y-s1.y)*(s4.y-s3.y)+(s2.z-s1.z)*(s4.z-s3.z));long double a2=b1;long double b2=srt(s4.x-s3.x)+srt(s4.y-s3.y)+srt(s4.z-s3.z);long double c1=(s1.x-s2.x)*(s1.x-s3.x)+(s1.y-s2.y)*(s1.y-s3.y)+(s1.z-s2.z)*(s1.z-s3.z);long double c2=(s1.x-s3.x)*(s4.x-s3.x)+(s1.y-s3.y)*(s4.y-s3.y)+(s1.z-s3.z)*(s4.z-s3.z);long double s=-(c2*b1-b2*c1)/(a1*b2-a2*b1);long double t=(a1*c2-a2*c1)/(a1*b2-a2*b1);// printf("s = %.6lf, t = %.6lf\n",s,t);ansp.x=s1.x+s*(s2.x-s1.x);ansp.y=s1.y+s*(s2.y-s1.y);ansp.z=s1.z+s*(s2.z-s1.z);ansq.x=s3.x+t*(s4.x-s3.x);ansq.y=s3.y+t*(s4.y-s3.y);ansq.z=s3.z+t*(s4.z-s3.z);ans = sqrt(srt(ansp.x-ansq.x)+srt(ansp.y-ansq.y)+srt(ansp.z-ansq.z));/* double e = (s2.y - s1.y)*(s4.z - s3.z) - (s4.y - s3.y)*(s2.z - s1.z);double f = (s2.z - s1.z)*(s4.x - s3.x) - (s4.z - s3.z)*(s2.x - s1.x);double g = (s2.x - s1.x)*(s4.y - s3.y) - (s4.x - s3.x)*(s2.y - s1.y);ans =(e*(s3.x-s1.x)+f*(s3.y-s1.y)+g*(s3.z-s1.z))/sqrt(fabs(e*e+f*f+g*g));*/printf("%.6lf\n",(double)ans);printf("%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf\n",(double )ansp.x,(double)ansp.y,(double)ansp.z,(double)ansq.x,(double)ansq.y,(double)ansq.z);}}

double ><

#include <cstdio>#include <cstring>#include <stack>#include <iostream>#include <cmath>#define inf 1000000000using namespace std;double x[5], y[5], z[5];double xx, yy, zz, xxx, yyy, zzz;double cal(double a, double b, double c, double d, double e, double f){return (sqrt((d-a)*(d-a)+(e-b)*(e-b)+(f-c)*(f-c)));}int main(){int cas;double A, B, C, D, E, F, o, aa, bb, cc, k;scanf("%d", &cas);while (cas--) {for (int i=1; i<=4; i++)scanf("%lf%lf%lf", &x[i], &y[i], &z[i]);A=x[2]-x[1]; B=y[2]-y[1]; C=z[2]-z[1];D=x[4]-x[3]; E=y[4]-y[3]; F=z[4]-z[3];aa=A*B*E-B*B*D-C*C*D+A*C*F;bb=A*A*E-A*B*D-B*C*F+C*C*E;cc=A*C*D-A*A*F-B*B*F+B*C*E;o=-x[1]*aa+y[1]*bb-z[1]*cc;k=(bb*y[3]-aa*x[3]-cc*z[3]-o)/(aa*D-bb*E+cc*F);xxx=D*k+x[3]; yyy=E*k+y[3]; zzz=F*k+z[3];A=x[4]-x[3]; B=y[4]-y[3]; C=z[4]-z[3];D=x[2]-x[1]; E=y[2]-y[1]; F=z[2]-z[1];aa=A*B*E-B*B*D-C*C*D+A*C*F;bb=A*A*E-A*B*D-B*C*F+C*C*E;cc=A*C*D-A*A*F-B*B*F+B*C*E;o=-x[3]*aa+y[3]*bb-z[3]*cc;k=(bb*y[1]-aa*x[1]-cc*z[1]-o)/(aa*D-bb*E+cc*F);xx=D*k+x[1]; yy=E*k+y[1]; zz=F*k+z[1];printf("%.6lf\n", cal(xx, yy, zz, xxx, yyy, zzz));printf("%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf\n", xx, yy, zz, xxx, yyy, zzz);}return 0;}

<代码非原创orz>