Складні маршрути
У підготовці до майбутніх Олімпійських ігор вас попросили розробити велосипедні маршрути для тренувань національної команди. Тренувальний комітет хоче визначити маршрути для поїздок між парами локацій на різних майданчиках по всій країні. Кожен маршрут повинен відповідати бажаному рівню складності, який залежить від крутизни його пагорбів.
Вам буде надано карту доріг з даними про висоту. Кожне перехрестя, де зустрічаються дві або більше доріг, визначається за його x-, y-, і z-координатами. Кожна дорога починається і закінчується на перехресті, є прямою і не містить мостів або тунелів. Рівень складності, d, для їзди на велосипеді по дорозі дорівнює 0, якщо дорога рівна або йде вниз по схилу. Складність дороги при підйомі вгору дорівнює 100*rise/run, де rise - це абсолютне значення зміни висоти, а run - це відстань між двома точками перетину в її горизонтальній проекції на 2D-площину на висоті нуль. Зверніть увагу, що складність для їзди на велосипеді по спуску дорівнює нулю.
Маршрут, що складається з послідовності доріг, де наступна дорога починається з того ж перехрестя, де закінчується попередня, має рівень складності d, якщо максимальний рівень складності серед усіх його доріг дорівнює d. Комітет також зацікавлений у виборі маршруту між двома обраними локаціями, якщо такий маршрут з бажаним рівнем складності існує, який має найкоротшу можливу відстань для подорожі.
Нагадування: Функція підлоги X означає X, усічене до цілого числа.
На малюнку показано карту доріг з трьома перехрестями для трьох прикладів вхідних даних.
Мітки на ребрах темнішої затіненої поверхні вказують рівень складності підйому вгору по схилу. Світліша затінена поверхня є горизонтальною проекцією на 2D-площину на висоті нуль.
Вхідні дані
Вхід складається з кількох карт доріг. Опис кожної карти починається з двох невід'ємних цілих чисел N і M, розділених пробілом на окремому рядку, які представляють кількість перехресть і кількість доріг відповідно. 0 < N, M ≤ 10000. Значення обох N і M, рівне нулю, позначає кінець вхідних даних.
Кожен з наступних N рядків містить три цілі числа, розділені одним пробілом, які представляють x-, y- і z-координати перехрестя. Цілі числа мають значення від 0 до 10000 включно. Перехрестя нумеруються в порядку їх появи, починаючи з значення один. Кожен з наступних M рядків містить два цілі числа, які представляють початкове і кінцеве перехрестя дороги.
Нарешті, три цілі числа s, t і d, які представляють бажаний номер початкового перехрестя s, кінцевого перехрестя t і рівень складності d для тренувального маршруту, наводяться на окремому рядку. Дійсний тренувальний маршрут повинен мати принаймні одну дорогу з рівнем складності d і жодної дороги з рівнем складності, що перевищує d. 0 ≤ d ≤ 10. Якщо тренувальний маршрут призначений для утворення замкнутого кола, то s і t є однаковими номерами перехресть.
Вихідні дані
Для кожної карти доріг і бажаного маршруту вихід складається з одного рядка, що містить:
число, що позначає найкоротшу довжину тренувального маршруту, округлену до одного десяткового знака, або
єдине слово "None", якщо жодного можливого маршруту не існує.
Нагадування: Округлення додатного числа R.xxxy до трьох десяткових знаків
Якщо четвертий десятковий знак менший за 5, то округлене значення є R.xxx
Інакше округлене значення є R.xxx + 0.001
Приклади: для значення 10.3463 вихід має бути 10.346, а для значення 10.3695 вихід є або 10.37, або 10.370
Нагадування: Округлення додатного числа R.xxxy до трьох десяткових знаків
• Якщо четвертий десятковий знак менший за 5, то округлене значення є R.xxx
• Інакше округлене значення є R.xxx + 0.001
Приклади: для значення 10.3463 вихід має бути 10.346, а для значення
10.3695 вихід є або 10.37, або 10.370