Welcome

首页 / 软件开发 / 数据结构与算法 / HDU 1174 爆头(三维空间点与直线关系)

HDU 1174 爆头(三维空间点与直线关系)2015-02-17HDU 1174:http://acm.hdu.edu.cn/showproblem.php?pid=1174

大意:中文题,很好理解,搞清楚各种变量就行。

思路:我知道的好像有两种解法,一种是求土匪的头心与子弹射出的直线求点到直线距离,在判断一下方向对不对;另一种是求出子弹射出点与土匪头心连线,求出子弹的射出的直线,求两直线的夹角, 求出子弹射出点与土匪头心连线,求出求出子弹射出点与土匪头的切线,求两直线的夹角,比较这两个夹角的大小判断是不是会打到。

这里我用第一种方法过的,就贴第一种的吧。

struct point{double x, y, z;} A, B, C; ///计算cross product U x Vpoint xmult(point u,point v){point ret;ret.x=u.y*v.z-v.y*u.z;ret.y=u.z*v.x-u.x*v.z;ret.z=u.x*v.y-u.y*v.x;return ret;} ///两点距离,单参数取向量大小double Distance(point p1,point p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));} ///矢量差 U - Vpoint subt(point u,point v){point ret;ret.x=u.x-v.x;ret.y=u.y-v.y;ret.z=u.z-v.z;return ret;} ///向量大小double vlen(point p){return sqrt(p.x*p.x+p.y*p.y+p.z*p.z);} double ptoline(point p,point l1,point l2){return vlen(xmult(subt(p,l1),subt(l2,l1)))/Distance(l1,l2);} int n;double h1,r1;double h2,r2,x3,y3,z3; void Solve(){scanf("%d", &n);while(n--){scanf("%lf%lf%lf%lf%lf", &h1, &r1, &A.x, &A.y, &A.z);scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &h2, &r2, &B.x, &B.y, &B.z, &C.x, &C.y, &C.z); A.z = A.z+h1-r1;B.z = B.z+h2*0.9-r2; double x = A.x-B.x;double y = A.y-B.y;double z = A.z-B.z;//printf("%lf %lf %lf
", x, y, z); point D; D.x = C.x+B.x;D.y = C.y+B.y;D.z = C.z+B.z; double d = ptoline(A, B, D);//printf("%lf
", d); if(d <= r1 && (x*C.x+y*C.y+z*C.z > 0)){printf("YES
");}else{printf("NO
");}}} HDU 1174
From:cnblogs GLSilence