Катастрофа та об'єднання

Гореліани — войовнича раса, яка мандрує Всесвітом, завойовуючи нові світи для розваги. Зазвичай їхні космічні битви проходять односторонньо, але іноді навіть гореліани зазнають поразки. Під час однієї з таких битв їхній корабель було настільки пошкоджено, що екіпажу довелося евакуюватися на планету. Через хаос (та неточність рятувальних капсул), гореліани виявилися розкиданими по великій площі планети (але досить малій, щоб її поверхню можна було моделювати як площину, а не кулю). Ваше завдання — відстежити їхні спроби зібратися разом. На щастя, кожна рятувальна капсула оснащена локатором, що показує координати посадки, і радіо для зв'язку з іншими гореліанами. На жаль, діапазон радіо обмежений доступною енергією.

Коли гореліанин приземляється, він насамперед перевіряє своє радіо: чи може він зв'язатися з іншими гореліанами? Якщо так, вони домовляються про зустріч у певній точці й збираються там. Зібравшись разом, вони об'єднують енергоресурси своїх радіо, збільшуючи радіус дії. Далі вони повторюють процес: кого можуть досягти, домовляються про зустріч, курсують до нового центру, поки не залишиться більше контактів з іншими гореліанами.

Технологія гореліан дозволяє двосторонній зв'язок, якщо хоча б один має радіо з достатнім діапазоном для покриття відстані між ними. Наприклад, якщо у Аліси радіус $40$ км, у Боба — $30$ км, але вони на відстані $45$ км один від одного, вони не можуть зв'язатися. Якщо ж відстань між ними $35$ км, то радіо Аліси досягне Боба, і зв'язок буде.

Якщо гореліан зв'язується з іншими, всі зустрічаються у точці, що є середнім арифметичним їхніх координат. У випадку Аліси й Боба це буде просто середина між $A$ і $B$. Поки рухаються до точки зустрічі, гореліани вимикають радіо й не виходять на зв'язок з іншими групами. На місці вони об'єднують радіо, і новий радіус визначається таким чином: сумарна площа покриття дорівнює сумі площ старих радіо. Наприклад, якщо у групи сукупно $1600\pi$ км^2 і $900\pi$ км^2 покриття, новий радіус $=50$ км, оскільки $2500\pi$ км^2 дорівнює площі круга з радіусом $50$. Після цього вони знову перевіряють, чи можуть досягти інші групи.

Процес повторюється, поки більше не можна контактувати з іншими. Наприклад, якщо приземлились (і мають радіус дії $30$ км): Аліса $(100,100)$, Боб $(130,80)$, Кеті $(80,60)$ і Дейв $(120,150)$ — зв'язатись не може ніхто. Коли приземляється Едді у точці $(90,80)$, він з'єднується з Алісою та Кеті, і вони трьома зустрічаються у $(90,80)$. Діапазон нової групи \sqrt{2700} \approx 51.96 км. Новий радіус діє вже й для Боба, група поповнюється, і вони зустрічаються у $(110,80)$, збільшуючи радіус до $60$ км. Але цього не вистачає, щоб дістати Дейва — він залишиться сам.