Ритуальне коло#6979

Ритуальне коло

60 секунд
64 мегабайти
Дуже складна

Перед від'їздом Братства з Рівенделлу, Більбо подарував Фродо свій ельфійський меч, який він називав Жало.

Цей меч був особливим: лезо світилося синім, коли поблизу були орки.

Вхідні дані

Вхід містить кілька тестових випадків. Кожен тестовий випадок складається з двох наборів точок на площині, що представляють позиції супутників Фродо та ворогів орків відповідно. Усі ці точки представлені цілими координатами зі значеннями компонентів від до включно. Кожна точка у кожному випадку є унікальною. Загальна кількість точок з обох наборів (супутники Фродо та орки) у будь-якому окремому випадку задачі не перевищує , і буде не більше тестових випадків з більш ніж точками.

Вихідні дані

Фродо потрібно визначити радіус найменшого кола, яке містить усі точки позицій його супутників і виключає всі точки позицій орків. Якщо таке коло не існує, то меч Жало світиться синім, і Фродо у небезпеці, тому виведіть "The Orcs are close". Якщо таке коло існує, виведіть радіус найменшого такого кола, заданий як десяткове значення з відносною похибкою не більше 1\text{e}-7.

У першому прикладі неможливо створити коло, яке включає обох супутників, але виключає обох орків; будь-яке таке коло повинно мати радіус принаймні певного значення, але будь-яке коло такого розміру повинно включати принаймні одного з орків.

У третьому прикладі коло може бути розміщене з центром на нескінченно малу відстань від у напрямку до точки , з радіусом, який є нескінченно більшим за певне значення.

Четвертий приклад є виродженим випадком з лише одним супутником, у якому коло з нульовим радіусом підходить.

Приклади

Приклад 1

Loading
Loading