가희와 btd5
시간 제한2.5초메모리 제한512 MB
원점에 있는 타워가 M번 광선을 발사하며, 각 광선은 같은 방향에 놓인 모든 풍선의 체력을 깎는다. 각 공격이 끝난 뒤 남은 풍선 수를 출력한다.
문제
btd5에는 Darting Gun Tower가 있습니다. Darting Gun Tower는 아래 알고리즘으로 풍선을 공격합니다.
- 공격하려는 목표물이 있는 방향으로 공격 방향을 바꿉니다.
- 공격 방향에 있는 풍선들의 체력을 d만큼 낮춥니다.
Darting Gun Tower는 좌표 (0, 0)에 하나 있습니다.
Darting Gun Tower가 공격하면, 공격 방향에 놓인 모든 풍선이 같은 수치의 피해를 입습니다.
처음에 풍선은 N개 있고, Darting Gun Tower는 M번 공격했습니다. 공격이 끝날 때마다 남은 풍선의 수를 세어 주세요.
초기 상태에서 Darting Gun Tower가 특정 방향으로 10⁹ 이상의 데미지로 공격하면, 모든 풍선을 제거하는 방법이 존재합니다.
입력
첫 번째 줄에 N, M이 주어집니다.
두 번째 줄부터 N+1번째 줄까지 풍선의 x좌표, y좌표, 체력이 주어집니다.
N+2번째 줄부터 N+M+1번째 줄까지 Darting Gun Tower의 공격 방향 (x, y)과 Darting Gun Tower가 준 데미지 d가 주어집니다.
출력
x번째 줄에 x번째 공격이 끝났을 때 남은 풍선의 개수를 출력해 주세요.
제한
- N과 M은 구간 [1, 2×10⁵]에 속하는 정수입니다.
- 풍선의 x 좌표와 y 좌표는 [-10⁹, 10⁹]에 속하는 정수입니다.
- 풍선의 위치는 고정되어 있으며, 풍선이 있는 위치에 Darting Gun Tower가 있지 않습니다.
- 두 개 이상의 풍선이 같은 위치에 있지 않습니다.
- 풍선의 hp와 Darting Gun Tower가 주는 데미지는 구간 [1, 10⁹]에 속하는 정수입니다.