hdu-1174 폭발(계산 기하학)

제목 링크:클릭 하여 링크 열기
폭발
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2093    Accepted Submission(s): 919
Problem Description
gameboy 는 CS 의 고수 이다.그 가 가장 좋아 하 는 것 은 경찰 역 을 맡아 M4 폭도 의 머리 를 들 고 있 는 것 이다.여기 서 CS 를 해 본 적 이 없 는 사람 이 있 을 지 모 르 지만'폭발'이라는 용 어 를 소개 할 필요 가 있다.이른바 폭발 이란 총알 이 상대방 의 머리 를 직접 명중 시 켜 적 을 순식간에 죽 이 는 것 이다.
현재 3 차원 직각 좌표계 로 게임 중의 3 차원 공간(수평면 은 xoy 평면 이 고 z 축의 정방 향 은 위쪽)을 묘사 합 니 다.게임 에서 캐릭터 의 머리 가 표준적 인 공이 라 고 가정 하 자.토비 의 키,머리 반경,서 있 는 위치의 좌 표를 알려 준다.gameboy 가 제어 하 는 경찰 의 키,머리 반경,서 있 는 위치의 좌표,그리고 총 머리 가 가리 키 는 방향의 단위 벡터.gameboy 가 통제 하 는 경찰 이 쥐 고 있 는 것 은 M4 입 니 다.제시간에 총 에 들 어 있 는 총알 과 시선 이 기본적으로 같은 선 입 니 다.우 리 는 그들의 거 리 를 무시 하고 같은 선 으로 생각 합 니 다.토비 가 AK 47 을 들 고 있 기 때문에 그 는 매우 날 뛰 며 똑바로 서 있다.반면 경찰 은 M4 를 들 고 조준 하고 있 었 다.조준 할 때 몸 이 약간 구 부 러 져 시선 이 머리 에서 출발 했 기 때문에 그의 머리 높이 는 정립 할 때 보다 10%낮 았 다.
당신 의 임 무 는 gameboy 가 이 순간 에 방 아 쇠 를 당 겨 토비 의 머리 를 터 뜨 릴 수 있 는 지 를 계산 하 는 것 입 니 다.주의:여 기 는 총알 의 직경 과 중력 작용 을 소홀히 한다.즉,총알 은 무한 하고 작고 탄 도 는 곧은 방사선 이 며 경찰 과 토비 사이 에는 장애물 이 없다.그리고 총알 이 머리 에 닿 으 면 가장자리 라 도 터 지 는 셈 이다.
 
Input
테스트 데이터 의 첫 줄 에는 T 조 테스트 데이터 가 있 음 을 나타 내 는 정수 T 가 있다.각 조 데이터 의 첫 줄 에는 다섯 개의 실수 가 있 는데 h1,r1,x1,y1,z1 은 토비 의 키,머리 반경 과 서 있 는 위 치 를 나타 낸다.두 번 째 줄 에는 8 개의 실수,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
   
   
   
   

제목 은 더 이상 말 할 필요 가 없 겠 지.경찰 키 조심 하 세 요.
고등학교 1 년 을 안 배 웠 더 니 공간 기하학 이 TUT 를 다 까 먹 었 어 요...................................................................결국 어 쩔 수 없 이 수량 적 구 를 썼 다.
가설 a=(x1,y1,z1),b=(x2,y2,z2)a*b=x1x2+y1y2+z1z 2|a|=√(x1^2+y1^2+z1^2+z1^2).|b|=√(x2^2+y2^2+z2^2)cosθ=a*b/(|a|*|b|)  이 공식 은 공간 임 의 두 벡터 사이 의 협각 을 구 한 후에 처리 하기 쉬 우 니 접선 을 해서 각 도 를 비교 하면 된다.각도 가 클 수록 cos 가 작 아 집 니 다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define eps 1e-8
struct people
{
   double h,r,x,y,z;
};
int main()
{
    int T;
    double x,y,z,a,b;
    people p,q;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lf %lf %lf %lf %lf",&p.h,&p.r,&p.x,&p.y,&p.z);
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&q.h,&q.r,&q.x,&q.y,&q.z,&x,&y,&z);
        q.z+=q.h*0.9-q.r;
        p.z+=p.h-p.r;
        double d=sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)+(p.z-q.z)*(p.z-q.z));
        double d1=sqrt(d*d-p.r*p.r);
        a=d1/d;
        double qpx=p.x-q.x,qpy=p.y-q.y,qpz=p.z-q.z;
        double num=qpx*x+qpy*y+qpz*z;
        double d2=sqrt(qpx*qpx+qpy*qpy+qpz*qpz);
        double d3=sqrt(x*x+y*y+z*z);
        b=num/(d2*d3);
        if(a-b<eps)
            printf("YES
");
        else
            printf("NO
");
    }
    return 0;
}