#2164 예측 샷

1 s   128 MB  

Description

예측 샷이란 게임에서 상대의 움직임을 예측하여 상대가 이동할 곳으로 미리 공격을 가하는 방법을 말한다. 예를 들어서, 움직이는 상대를 맞추기 위하여 상대가 서있는 곳으로 미사일을 발사하여도, 미사일이 도착할 쯤에는 상대가 이동하여 맞지 않을 확률이 크다. 그래서 상대가 이동할 곳을 예측하여 그 곳으로 미리 발사를 하면 상대를 맞출 수도 있고, 상대의 진로를 방해할 수도 있다.

창구씨는 요즘 유행하는 게임 ‘Catch the teemo’에 푹 빠져있다. ‘Catch the teemo’는 유저가 선택한 한 캐릭터를 사용하여, 도망다니는 티모를 잡는 게임이다. 창구씨가 플레이하고 있는 캐릭터는 ‘르블랑’이라는 캐릭터로 ‘환영 사슬’이라는 기술을 사용할 수 있다. ‘환영 사슬’을 사용할 경우, 한 방향으로 사슬을 발사할 수 있는데, 이 사슬은 일정한 속력으로 직선으로 나아가게 된다. 사슬의 머리에 물체가 닿게 될 경우, 사슬은 해당 물체를 포박하게 된다.

티모는 2차원 게임 세상에서 항상 일정한 방향과 속도로 움직이고 있으며, 반지름이 r인 원의 모양을 하고 있다. 

예측 샷 그림설명

위 그림처럼 평면상에서 직선으로 수풀을 뛰어다니는 티모의 위치(T)와 속도 벡터(VT), 그리고 티모의 반지름(r)이 주어진다. 또한 르블랑의 현재 위치(L)와 환영 사슬의 속도 벡터 (VE)가 주어질 때, 이 사슬은 티모를 포박할 수 있는 지 판단하는 프로그램을 작성하시오.

모든 위치와 방향 벡터는 좌표 형식(x, y)로 주어지며, 속도 벡터는 1초당 움직이는 정도를 표현한다. 사슬의 머리는 부피가 없는 점으로 생각하고 문제를 해결한다. 사슬의 머리가 티모의 몸체에 닿으면 티모는 포박되며, 이미 사슬이 지나간 자리는 날쌘 티모가 뛰어넘고 지나갈 수 있다고 가정한다. 

Input

첫 줄에 테스트 케이스 C (1 ≦ C ≦ 100) 가 주어진다.

각 테스트 케이스의 첫 줄에는 티모의 반지름 R (1 ≦ R ≦ 100) 이 정수로 주어진다. 두 번째 줄에는 티모의 위치와 속도 벡터가 좌표 형식으로 주어진다. 세 번째 줄에는 르블랑의 위치와, 환영 사슬의 속도 벡터가 좌표 형식으로 주어진다.

모든 위치와 속도 벡터의 좌표는 -1,000 ~ 1,000 사이의 정수로 주어진다. 단, 범위는 처음 입력에서만 적용되며, 티모나 사슬이 속도 벡터를 따라 이동하여 범위를 넘어가는 것은 가능하다. 

Output

각 케이스 별로 한 줄에 결과를 출력한다. 사슬이 티모를 포박할 수 있으면 “Teemo died.”를 출력하고, 포박할 수 없으면 “Teemo has to die.”를 출력하라.

Sample Input

Sample Output

2
1
0 0 1 0
1 1 0  -1
2
1 1 1 1
-1 -2 -2 -2
Teemo died.
Teemo has to die.

Source

2014 Ajou Programming Contest, Division 1∙2 - 김동이 (mitslll, 아주대학교)