首页 > ACM题库 > HDU-杭电 > HDU 1174 爆头-计算几何-[解题报告] C++
2013
12-03

HDU 1174 爆头-计算几何-[解题报告] C++

爆头

问题描述 :

gameboy是一个CS高手,他最喜欢的就是扮演警察,手持M4爆土匪的头。也许这里有人没玩过CS,有必要介绍一下“爆头”这个术语:所谓爆头,就是子弹直接命中对方的头部,以秒杀敌人。

现在用一个三维的直角坐标系来描述游戏中的三维空间(水平面为xoy平面,z轴正方向是上方)。假设游戏中角色的头是一个标准的球。告诉你土匪的身高,头部半径,所站位置的坐标;gameboy所控警察的身高,头部半径,所站位置的坐标,以及枪头所指方向的单位向量。gameboy所控警察所握的是M4,抢瞄准时枪膛中的子弹跟视线基本同线,我们忽略它们的距离,就当成同线。由于土匪手持AK47,所以他是很嚣张地正立着。而警察手持M4,正在瞄准,由于瞄准时身体微弯,视线从头心出发,他头部的实际高度比正立时低10%。

你的任务就是,计算gameboy在这一刻扣下扳机,能否爆土匪的头。注意:这里忽略子弹的直径和重力作用,也就是说子弹是无限小的,弹道是一条笔直的射线,警察与土匪间没有障碍物。并且只要子弹擦到头部,哪怕是边缘,也算爆头。

输入:

测试数据的第一行有一个正整数T,表示有T组测试数据。每组数据的第一行有五个实数,h1,r1,x1,y1,z1,分别表示土匪的身高,头部半径以及所站的位置。第二行有八个实数,h2,r2,x2,y2,z2,x3,y3,z3,分别表示警察的身高,头部半径,所站位置,以及枪头所指方向的方向向量。

输出:

每一组输入数据对应一行输出。如果能爆土匪的头,输出"YES",否则输出"NO"。

样例输入:

2
1.62 0.1 10.0 10.0 10.0
1.80 0.09 0.0 0.0 0.0 1.0 1.0 1.0
1.62 0.1 0.0 0.0 0.0
1.80 0.09 10.0 10.0 10.0 -1.0 -1.0 -1.0

样例输出:

YES
YES

点击打开链接

给你站在三维空间的警察和土匪的身高,头部半径,坐标。还有警察枪的方向向量

判断是否可以爆头

补充知识:

差乘

向量a=(x1,y1,z1)  b=(x2,y2,z2)

a
x(差乘) b=( y1z2 – z1y2 , z1x2 – x1z2 , x1y2-y1x2)

点到直线的距离可以用等面积做

B到直线AC的距离可以用
|AB差乘AC|/|AC|

#include"stdio.h"
#include"math.h"
int main()
{
    int t;
    double h1,r1,x1,y1,z1;
    double h2,r2,x2,y2,z2;
    double x3,y3,z3;
    double x,y,z;
    double dis,a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf%lf",&h1,&r1,&x1,&y1,&z1);
        scanf("%lf%lf%lf%lf%lf",&h2,&r2,&x2,&y2,&z2);
        scanf("%lf%lf%lf",&x3,&y3,&z3);
        z1=z1+h1-r1;//土匪头部Z轴坐标
        z2=z2+h2*0.9-r2;//警察头部Z轴坐标
        x=x1-x2;//土匪头部与警察头部连线向量
        y=y1-y2;
        z=z1-z2;
        a=y*z3-z*y3;//手枪的方向向量与警察与土匪连线的差乘
        b=z*x3-x*z3;
        c=x*y3-y*x3;
        dis=sqrt((a*a+b*b+c*c)/(x3*x3+y3*y3+z3*z3));
        if(dis<=r1&&(x*x3+y*y3*z*z3>0)) r1处也可以写成r2,红色部分是判断土匪在警察面前而不是身后。。
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  5. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?