Hdu 1174 爆頭 計算幾何問題

NO IMAGE
目錄

爆頭

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1744    Accepted Submission(s): 732

Problem Description
gameboy是一個CS高手,他最喜歡的就是扮演警察,手持M4爆土匪的頭。也許這裡有人沒玩過CS,有必要介紹一下“爆頭”這個術語:所謂爆頭,就是子彈直接命中對方的頭部,以秒殺敵人。

現在用一個三維的直角座標系來描述遊戲中的三維空間(水平面為xoy平面,z軸正方向是上方)。假設遊戲中角色的頭是一個標準的球。告訴你土匪的身高,頭部半徑,所站位置的座標;gameboy所控警察的身高,頭部半徑,所站位置的座標,以及槍頭所指方向的單位向量。gameboy所控警察所握的是M4,搶瞄準時槍膛中的子彈跟視線基本同線,我們忽略它們的距離,就當成同線。由於土匪手持AK47,所以他是很囂張地正立著。而警察手持M4,正在瞄準,由於瞄準時身體微彎,視線從頭心出發,他頭部的實際高度比正立時低10%。

你的任務就是,計算gameboy在這一刻扣下扳機,能否爆土匪的頭。注意:這裡忽略子彈的直徑和重力作用,也就是說子彈是無限小的,彈道是一條筆直的射線,警察與土匪間沒有障礙物。並且只要子彈擦到頭部,哪怕是邊緣,也算爆頭。

 

Input
測試資料的第一行有一個正整數T,表示有T組測試資料。每組資料的第一行有五個實數,h1,r1,x1,y1,z1,分別表示土匪的身高,頭部半徑以及所站的位置。第二行有八個實數,h2,r2,x2,y2,z2,x3,y3,z3,分別表示警察的身高,頭部半徑,所站位置,以及槍頭所指方向的方向向量。
 

Output
每一組輸入資料對應一行輸出。如果能爆土匪的頭,輸出”YES”,否則輸出”NO”。
 

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

Sample Output
YES
YES
 

Author
lwg
溫馨提示:這是一道很好的幾何問題,可以理解為求空間上點到直線的距離,即土匪頭部中心到警察槍所在直線的距離。這裡我們要用到三維差乘求點到直線的距離,例如向量AB叉乘向量AC的模再除以向量AC的模就的到了B到AC的距離。將土匪頭部中心當做點B,土匪和警察的連線看做是向量AB,警察的槍看做是向量AC。
<span style="font-size:18px;">#include <iostream>
#include <cmath>
using namespace std;
//差乘公式:向量AB叉乘向量AC的模再除以向量AC的模就的到了B到AC的距離;
double chacheng(double x1,double y1,double z1,double x2,double y2,double z2)
{
double a, b, c;
a = y1*z2-z1*y2;
b = x1*z2-z1*x2;
c = x1*y2-y1*x2;
return sqrt((a*a b*b c*c))/sqrt((x2*x2 y2*y2 z2*z2));
}
int main()
{
int T;
double h1,r1,x1,y1,z1;
double h2,r2,x2,y2,z2,x3,y3,z3;
double a,b,c,dis;
cin>>T;
while (T--)
{
cin>>h1>>r1>>x1>>y1>>z1;
cin>>h2>>r2>>x2>>y2>>z2>>x3>>y3>>z3;    //(x3,y3,z3)代表方向向量
z1  = h1-r1;
z2  = h2*0.9-r2;
a = x1-x2;
b = y1-y2;
c = z1-z2;
dis = chacheng(a,b,c,x3,y3,z3);
if(dis<=r1 && (a*x3 b*y3 c*z3)>0)   //(a*x3 b*y3 c*z3)>0是為了判斷匪徒是不是在警察正面
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}</span>