Аварія та Go(реліани)
The Gorelians — це войовнича раса, яка подорожує всесвітом, завойовуючи нові світи для розваги. Зазвичай їхні космічні битви проходять односторонньо, але іноді навіть Gorelians зазнають поразки. Під час однієї з таких битв їхній космічний корабель був настільки пошкоджений, що їм довелося евакуюватися на планету внизу. Через хаос (і неточність рятувальних капсул) Gorelians розкидані по великій площі планети (але досить малій, щоб моделювати її поверхню як площину, а не сферу). Ваше завдання — відстежити їхні зусилля щодо об'єднання. На щастя, кожна рятувальна капсула оснащена локатором, який повідомляє Gorelian його поточні координати на планеті, а також радіо для зв'язку з іншими Gorelians. На жаль, діапазон радіо обмежений кількістю доступної енергії.
Коли Gorelian приземляється на чужій планеті, перше, що він робить, — це перевіряє радіо, щоб дізнатися, чи може зв'язатися з іншими Gorelians. Якщо так, то домовляється про місце зустрічі, і вони збираються в цій точці. Зібравшись, вони об'єднують джерела живлення своїх радіо, збільшуючи радіус дії. Потім вони повторюють процес — перевіряють, кого можуть досягти, домовляються про зустріч, об'єднують радіо — поки не зможуть зв'язатися з усіма іншими Gorelians.
Технологія Gorelian дозволяє двосторонній зв'язок, якщо хоча б один з них має радіо з достатнім діапазоном для покриття відстані між ними. Наприклад, якщо у Аліси радіо з діапазоном 40 км, а у Боба — 30 км, але вони знаходяться на відстані 45 км один від одного (Рисунок 1), вони не можуть спілкуватися. Однак, якщо відстань між ними 35 км (Рисунок 2), радіо Аліси може досягти Боба, і вони можуть спілкуватися.
Якщо Gorelian успішно зв'язується з іншими, вони зустрічаються в точці, яка є середнім значенням їхніх місць розташування. У випадку з Алісою та Бобом це буде середина між A і B (Рисунок 3). Gorelians вимикають свої радіо під час подорожі; вони не намагатимуться спілкуватися з іншими, поки всі не зберуться в місці зустрічі. Коли Gorelians зустрічаються, вони об'єднують свої радіо, створюючи нове з більшим діапазоном. Зокрема, площа, покрита новим радіо, дорівнює сумі площ, покритих старими радіо. Наприклад, якщо у Аліси діапазон 40 км, її радіо покриває площу 1600π км. Радіо Боба покриває 900π км. Об'єднуючи їх, вони покривають 2500π км, тобто мають діапазон 50 км. Потім вони знову намагаються зв'язатися з іншими Gorelians.
Цей процес триває, поки не можна буде зв'язатися з іншими Gorelians. Наприклад, припустимо, що наступні Gorelians всі приземлилися і мають радіус дії 30 км: Аліса (100, 100), Боб (130, 80), Кеті (80, 60) і Дейв (120, 150). Жоден з них не може зв'язатися з іншим (Рисунок 5). Потім Едді приземляється на позиції (90, 80) (Рисунок 6). Едді може зв'язатися з Алісою та Кеті, тому вони домовляються зустрітися в точці (90, 80), середньому значенні їхніх місць розташування. Об'єднання їхніх радіо дає їм діапазон √2700 ≈ 51.96 км (Рисунок 7).
Тепер вони перевіряють з новим діапазоном і виявляють, що можуть досягти Боба. Вони зустрічаються з Бобом у точці (110, 80) і об'єднують радіо, отримуючи діапазон 60 (Рисунок 8). На жаль, цього недостатньо, щоб досягти Дейва, тому Дейв залишається ізольованим.
Вхідні дані
Вхідні дані складатимуться з одного або більше наборів даних. Кожен набір даних починатиметься з цілого числа, що представляє кількість Gorelians у цьому наборі (1 ≤ ≤ 100). Значення = 0 означатиме кінець введення.
Далі йтимуть рядки, кожен з яких містить три цілі числа , , і , що представляють x- та y-координати, де приземляється Gorelian, та діапазон радіо (0 ≤ ≤ 1000, 0 ≤ ≤ 1000, і 1 ≤ ≤ 1000). Зверніть увагу, що лише початкові координати/діапазон Gorelians будуть цілочисельними; після об'єднання з іншими Gorelians вони можуть більше не бути цілочисельними. Ви повинні використовувати арифметику з подвійною точністю для всіх обчислень.
Gorelians приземляються в порядку, в якому вони з'являються у вхідному файлі. Коли Gorelian приземляється, він об'єднується з будь-якими Gorelians, з якими може зв'язатися, і процес продовжується, поки не можна буде зробити подальші об'єднання. Наступний Gorelian не приземляється, поки всі попередні об'єднання не будуть завершені.
Вихідні дані
Вихідні дані міститимуть один рядок на кожен набір даних, в якому повідомляється кількість незалежних груп Gorelians, що залишаються в кінці процесу.