Задача SugarBoy. Цукрові хлопчики зовсім не люблять воду. Цукровий хлопчик Оллі застряв у системі печер і тунелів. Раптом в одній з печер пробилося джерело води. Оллі хоче знати, скільки часу у нього є, поки вода не дійде до нього. Можливо, що вода ніколи не дійде до нього, за що Оллі, безперечно, буде дякувати небесам. Оллі знає, як облаштовані печери і яким чином вода заповнює тунелі. Отже:
- усі печери – порожнисті сфери діаметром 1м. Центри печер на плані розміщені у цілочисельних точках;
- деякі печери з’єднані тунелями. Усі тунелі прямі і з’єднують межу однієї печери з межею іншої. Пряма, якій належить тунель, що з’єднує 2 печери, пройде через центри печер, які з’єднуються цим тунелем;
- джерело пробивається в центрі певної печери. Продуктивність джерела - 1 кубічний метр за секунду
- вода починає наповнювати стартову печеру. Щойно вода доходить до рівня певного тунелю, вся вода, що прибуває, витікає у цей тунель, поки не наповнить усю систему печер, у яку прокладено цей тунель. Як тільки це відбулося, у стартовій печері вода продовжує накопичуватися. Це відбувається до того моменту, поки рівень води не дійде до наступного тунелю. Далі все повторюється - спершу наповнюється система печер, до якого цей тунель іде, а потім вже продовжує наповнюватись поточна печера. Ніяка два тунелі не сполучені безпосередньо між собою;
- вода не тече з печери рівнем нижче у печеру рівнем вище:
- тунелі і печери розміщені таким чином, що у жодній печері немає тунелів з однаковим рівнем. Крім того, немає з’єднаних печер з однаковим рівнем (тобто горизонтальним тунелем);
- джерело у початковій печері перестає працювати, як тільки ця печера повністю заповниться.
Технічні умови. Програма 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 тунелями, цукровому хлопчику стане непереливки - у його печері стане занадто волого. |