Missile Command
Як Головний Бюрократ у Командуванні Ракетами, ви дізналися, що чинні керівні принципи продуктивності недостатньо карають за легковажне використання дорогої амуніції. Тому вам потрібно розробити новий інструмент для аналізу підсумків бою, який враховує надмірне використання амуніції під час бою.
Бій складається з таких елементів:
Постріли. Постріл є круговою вибуховою протидією. Він має фіксовану позицію і триває 2 секунди, протягом яких його радіус змінюється від 0 до 1 км і потім назад до 0 за формулою: r = sqrt(1 – (t – 1) ^ 2).
Земля, на y = 0.
Ракети. Ракета є точковою частинкою, яка рухається з постійною швидкістю. Якщо ракета стикається з пострілом, вона нейтралізується. Якщо ракета влучає в землю до нейтралізації, вважається, що вона влучила в ціль.
ПРИМІТКА 1: Якщо ракета влучає в постріл, постріл не зникає - він може влучити в інші ракети.
ПРИМІТКА 2: Постріли з радіусом 0 не можуть влучити в ракети (наприклад, ракета пройде через вже завершений постріл).
Продуктивність оцінюється за простою шкалою балів. Критерії продуктивності такі:
Кожна нейтралізована ракета додає 1 бал.
Кожна ракета, що влучила в ціль, віднімає 5 балів.
Кожен зайвий постріл віднімає 20 балів. Кількість зайвих пострілів у бою - це різниця між фактичною кількістю пострілів і розміром мінімальної підмножини цих пострілів, які б нейтралізували таку ж кількість ракет.
Вхідні дані
Вхідні дані будуть надані у наступному форматі (легенда нижче):
nb
nm
mx my mdx mdy mt
...
ns
sx sy st
...
...
У наступній легенді відступ означає повторення відступленого блоку кількість разів, рівну значенню попереднього елемента вхідних даних:
nb (0 < nb) – кількість боїв
nm (0 ≤ nm ≤ 20) – кількість ракет
mx/my (0.0 < my) – початкова позиція ракети (в км)
mdx/mdy – швидкість ракети (в км/с)
mt (0.0 ≤ mt) – час з початку бою, коли ракета з'являється (в секундах)
ns (0 ≤ ns ≤ 20) – кількість пострілів
sx/sy (1.0 ≤ sy) – позиція пострілу в момент детонації (в км)
st (0.0 ≤ st) – час з початку бою, коли відбувається детонація пострілу (в секундах)
Вихідні дані
Для кожного бою виведіть рядок, що містить оцінку за цей бій.