#1775 터렛

15  1 s   128 MB  

Description

 


스타크래프트2에 있는 터렛이라는 건물이 있다.
 
터렛은 공중 공격만 할 수 있으며, 유클리드 거리로 R이하에 있는 비행물체 1기를 A초마다 데미지 B짜리로 한번만 공격 할 수가 있다. 공격을 당한 유닛은 B만큼의 체력이 깎이게 된다.
 
터렛은  0, A, 2A, 3A, 4A, 5A, 6A, ...   초 일 경우에만 터렛이 미사일을 쏠 수 있다(단 미사일은 발사 즉시 목표물에 적중한다.)
 
터렛은 항상 2차원 좌표계에 (0,0)에 위치해 있으며, 무한한 2차원 좌표 평면에서 유닛들이 일정속도로 지나다닌다. 편의상 유닛에 1번 부터 N 번 까지 번호가 붙어있다.
 
유닛들은 처음에 (Xi,Yi)(처음에 같은 좌표상에 두개 이상의 유닛이 존재할 수 없다) 위치해 있으며, 1 초마다 현재 위치에서 x값이 Vxi 만큼,  y값이 Vyi만큼 이동한다.
유닛은 지상 유닛,공중 유닛, 지상&공중유닛 3종류가 존재하며, 평면상에서 점으로 가정한다.
 
각 유닛은 처음에 HPi 만큼의 체력을 가지고 있으며, 공격을 받아 체력이 0이하가 되면 파괴된다. 터렛은 지상 유닛을 제외한 공중 유닛,지상&공중유닛을 공격 할 수 있다.
 
만약 거리 R이하에 유닛이 여럿 있을 경우 존재 한다면 번호가 가장 작은 유닛을 공격 하게 된다.
 
아래 첫번째 예제의 초기 상태를 그림으로 표현하면 그림 1과 같다. 그림에서 동그라미는 공중 유닛 혹은 지상\&공중 유닛을 뜻하고, 삼각형은 지상 유닛을 뜻한다.
 
첫번째 테스트 케이스의 초기상태
그림1. 첫번째 테스트 케이스의 초기 상태
 
0초 때  (-1,0)에 존재하는 공중유닛은 터렛에게 공격을 당해 파괴 된다. 
그 다음 지상유닛은 시간이 아무리 지나도 맞질 않기때문에 살아 남게 되고, 지상&공중유닛은 3초,4초,5초에 공격을 당한 다음 체력이 2가 남고 더이상 공격을 받지 않기 때문에 파괴되지 않는다.
 
세번째 테스트 케이스에 대해 0초 부터 3초 까지의 상황을 그림으로 표현하면 그림 2와 같다.
그림 2. 세번째 테스트 케이스의 0초부터 3초까지의 상태
t = 0 t = 1 t = 2 t = 3
 
 
0초 때  (-1,0)에 존재하는 2번 공중 유닛은 터렛에게 공격을 당하고 체력이 1이 된다. 그 다음 1초뒤에는 번호가 더 빠른 유닛이 공격 범위에 
포함 되고, 1번 유닛이 공격을 받게 되지만, 그 뒤에 공격을 받지 않는다. 3번 유닛의 경우 어떠한 공격을 받지 않게 되며, 결과적으로 모든 유닛이 생존한다.
 
터렛의 정보와 유닛들의 정보가 주어졌을 때 1,000초가 지났을 때 파괴되지 않고 살아 있는 유닛의 수를 찾아내는 프로그램을 작성하라.
 

 

Input

첫 줄에는 테스트 케이스의 수 T 가 주어진다( 1 ≤ T ≤ 100 )

그 다음 줄에는 터렛의 공격속도 A와, 터렛이 유닛에게 한번 공격 할 때 입히는 데미지 B와 터렛의 사정거리 R 이 입력된다 ( 1 ≤ A ≤ 10, 1 ≤ B ≤ 1, 000, 1 ≤R ≤ 1, 000 ).

그 다음 줄에는 유닛의 수 N(1 ≤ N ≤ 500)이 입력되고, 그 아래 N 줄에는 유닛의 정보들이 입력되며 다음과 같은 형태로 입력되며, 입력된 순서대로 1번 유닛의 정보, 2번 유닛의 정보, . . . , N 번 유닛의 정보를 뜻한다.
입력되는 숫자 사이에는 반드시 공백이 존재하며, 모든 숫자는 정수 형태로 이뤄져 있다. 
typei,Xi, Yi, V xi, V yi,HPi
 
typei 이 1일 경우 i번 유닛은 지상유닛, 2일 경우 공중유닛, 그리고 3은 지상&공중유닛이다. ( −1, 000 ≤ x, y ≤ 1, 000,−50 ≤ V xi, V yi ≤ 50, 1 ≤ HPi ≤ 500 )

 

Output

각 테스트 케이스에 대해 1,000초 이후에 살아 남은 유닛의 수를 한줄에 하나씩 입력된 테스트 케이스 순서대로 출력한다.

Sample Input

Sample Output

3
1 1 1
3
1 -5 0 1 0 1
2 -1 0 1 0 1
3 0 5 0 -1 5
1 1 1
3
2 -5 0 -1 0 1
2 -1 0 1 0 5
2 0 5 0 -10 1
1 1 1
3
2 -2 0 1 0 4
2 -1 0 1 0 2
2 0 5 0 -10 1
2
3
3

HINT

두개의 좌표 P1 = (x1, y1), P2 = (x2, y2) 간의 유클리드 거리 d(P1, P2) 는 다음과 같이 계산한다.

d(P1, P2) = ((x1 − x2)^2 + (y1 − y2)^2)^(1/2)

Source

2011 Ajou University Programming Contest, Division 2