Задача SugarBoy. Цукрові хлопчики зовсім не люблять воду. Цукровий хлопчик Оллі застряв у системі печер і тунелів. Раптом в одній з печер пробилося джерело води. Оллі хоче знати, скільки часу у нього є, поки вода не дійде до нього. Можливо, що вода ніколи не дійде до нього, за що Оллі, безперечно, буде дякувати небесам. Оллі знає, як облаштовані печери і яким чином вода заповнює тунелі. Отже:
Технічні умови. Програма SugarBoy читає з пристрою стандартного введення числа N, M, A, B (2 ≤ N ≤ 100, 0 ≤ M ≤ N*(N-1)/2 , 1 ≤ A, B ≤ N) ) - кількість печер і кількість тунелів, а також номер печери, де пробилося джерело і номер печери, де стоїть Оллі. Далі слідують N пар цілих чисел (кожне за модулем не перевищує 5000), кожна з яких задає позицію центру чергової печери. Після цього слідують рівно M пар цілих чисел - номери печер, які з’єднує черговий тунель. Програма має виводить два рядки. Перший рядок містить SAFE, якщо Оллі нічого не загрожує або ж DANGER, якщо вода рано чи пізно дійде до Оллі. У першому випадку другий рядок повинен містити час, за який джерело у початковій печері перестане наповнюватись. У другому випадку слід вивести час, через який перша крапля води потрапить до печери Оллі. У обох випадках виведіть шукану величину у секундах з абсолютною точністю не гірш ніж у 3 знаки після коми.
Приклади:
Введення |
Виведення |
Коментар |
2 1 1 2 0 0 2 2 1 2
|
SAFE 0.523598 |
Перша і друга печери хоч і з’єднані, але друга печера вище, тому вода туди не потрапить. Джерело перестане текти, коли перша печера (об’ємом приблизно у 0.523598 метрів кубічних) повністю заповниться, тобто через 0.523598 секунди |
6 6 1 4 1 2 5 0 2 -1 9 -1 4 -4 4 -2 1 2 2 4 2 6 6 5 3 6 3 5 |
DANGER 1.3135079 |
Через деякий час після початку заповнення 1ої печери вода потрапить до другої. Там вона через деякий час піде у печеру номер 6, звідки одразу потече у печеру номер 5. Після наповнення п’ятої печери почне заповнюватись і печера номер 6. Як тільки вона заповниться, вода почне наповнювати другу печеру (у якій вже є деяка кількість води). Як тільки вода наповнить печеру до рівня тунелю між 2 і 4 тунелями, цукровому хлопчику стане непереливки - у його печері стане занадто волого. |
© LIKT 1998-2018