Лопання повітряних кульок#3123
Джон обожнює змагання з програмування. Є лише одна проблема: його команда не дуже добре програмує. Зазвичай це його не турбує, але йому дуже не подобається, що за кожне правильне розв'язання всі отримують повітряну кульку. Команда Джона ніколи не отримує кульок, а інші команди отримують одну за одною. Це його дратує, тож Джон хотів би, щоб і інші команди не мали кульок.
Цього року він придумав план. Джон найняв ніндзя, щоб той луснув всі кульки за нього. У будь-який момент змагання він може покликати ніндзя спуститися крізь отвір у стелі, використати шурікени (зірки ніндзя), щоб луснути всі кульки, і знову зникнути через отвір. Звісно, ніндзя хоче використати якомога менше своїх дорогоцінних шурікенів. Тому Джон має написати програму, яка підрахує, скільки шурікенів потрібно, щоб луснути всі кульки. Оскільки всі кульки знаходяться приблизно на одній висоті, він може звести задачу до двовимірної моделі. Він задає місце появи ніндзя як початок координат і використовує кола для моделювання кульок. Для безпеки ці кола можуть мати різні радіуси. Шурікени кидаються з початку координат і рухаються по прямій. Будь-яке коло/кулька, яке ця лінія перетинає, буде луснуте шурікеном. Питання таке: скільки потрібно напрямків прямих, що проходять через початок координат, щоб перетнути всі кола?
Як згадувалося вище, Джон не дуже добре програмує, тож просить вас написати цю програму за нього. Чи зможете ви допомогти йому? Можливо, за правильну відповідь ви отримаєте кульку...
Рисунок 1. Другий приклад із введення
Перший рядок містить одне ціле число: кількість тестових випадків у подальшому. Кожен тестовий випадок має наступний формат:
Рядок з одним цілим числом (0 \le n \le 1\,000): кількість кульок.
рядків, кожен з яких містить три цілі числа x_i, y_i (-10^4 \le x_i, y_i \le 10^4) і r_i (1 \le r_i \le 10^4), що описують -ту кульку у вигляді кола з центром у (x_i, y_i) та радіусом r_i.
Можна вважати, що дві прямі (які виходять з початку координат), дотичні до двох різних кіл, утворюють кут при початку координат не менше ніж 10^{-6} радіан. Крім того, жодні два кола не перетинаються (але можуть торкатись), і жодне коло не містить початок координат.
Для кожного тестового випадку виведіть одне ціле число: мінімальну кількість шурікенів, які ніндзя повинен використати, щоб луснути всі кульки.
Приклад 1