eolymp
bolt
Try our new interface for solving problems
Məsələlər

Путешествие Джейна

Путешествие Джейна

Zaman məhdudiyyəti 75 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Капитан Джейн хочет провести свой корабль "Вояжер" через поле астероидов, однако их имеется слишком большое количество для безопасной поездки. Чтобы помочь ему проложить путь, Вас попросили исследовать поле астероидов. Ваш план состоит в том, чтобы пролететь по полю и составить его план. Затем следует установить Ваш корабль с лазерной пушкой впереди таким образом, чтобы уничтожить как можно больше астероидов с помощью одного прямого выстрела лазерного луча.

Для простоты мы будем моделировать эту задачу в плоскости, где астероиды представлены кругами, лазерный луч является бесконечно тонким, а Ваш корабль можно установить где угодно и как угодно, внутри или снаружи астероидного поля.

Giriş verilənləri

Первая строка содержит количество тестов t (1 t 25). Каждый тест начинается с количества астероидов n (1 n 2000). Далее следует не более 5 тестов у которых n > 500. Каждая из следующих n строк содержит 3 действительных числа x_i, y_i, r_i означающих что астероид i имеет центр (x_i, y_i) и радиус r_i (-10^{6 }x_i, y_i10^6, 1 r_{i }100). Все значения заданы с точностью до двух десятичных знаков. Никакие два астероида не перекрываются и не пересекаются. Входные данные таковы, что ответ не изменится если радиусы астероидов изменить 10^{-6} в любом направлении.

Çıxış verilənləri

Для каждого теста вывести в отдельной строке наибольшее количество астероидов, которое можно уничтожить.

Nümunə

Giriş verilənləri #1
1
3
0.00 0.00 1.00
3.00 0.00 1.00
3.00 3.00 1.00
Çıxış verilənləri #1
2
Mənbə 2013 North America - Pacific Northwest Region Programming Contest, Задача J