1. SugarBoy

Задача   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 тунелями, цукровому хлопчику стане непереливки - у його печері стане занадто волого.

 

© LIKT 1998-2018