Психічний Акселератор
На заході Токіо розташоване місто під назвою "Академічне місто". Це місце відоме своїми численними школами та лабораторіями, де розвивають екстрасенсорні здібності.
Ви є студентом-екстрасенсом в одній із цих шкіл. Ваша унікальна здатність полягає в тому, щоб надавати прискорення певному об'єкту.
Ви можете використовувати свою здатність у будь-який час і в будь-якому місці, але є певні обмеження. Якщо об'єкт нерухомий, ви можете надавати йому прискорення в будь-якому напрямку. Якщо ж об'єкт рухається, ви можете прискорювати його лише в 1) напрямку руху, 2) протилежному напрямку, або 3) перпендикулярному напрямку.
Сьогоднішнє завдання полягає в тому, щоб перемістити об'єкт уздовж заданого маршруту. Для спрощення вважайте, що маршрут складається з прямих відрізків та дуг у двовимірному просторі. Маршрут не має розгалужень. Усі відрізки та дуги з'єднані плавно, без гострих кутів.
На початку об'єкт знаходиться в початковій точці першого відрізка. Ви повинні перемістити його до кінцевої точки останнього відрізка, контролюючи прискорення так, щоб об'єкт зупинився в кінцевій точці.
Перед тренуванням тренер попросив вас змоделювати мінімальний час, необхідний для переміщення об'єкта з початкової точки до кінцевої.
Ваше завдання — написати програму, яка зчитує форму маршруту та максимальне прискорення amax, яке ви можете надати об'єкту, і обчислює мінімальний час для переміщення об'єкта з початкової точки до кінцевої.
Об'єкт підкоряється основним фізичним законам. Коли об'єкт рухається прямо в якомусь напрямку, з прискоренням вперед або назад, діють такі рівняння:
v = v_0 + at
та
s = v_0t +1/2at^2
де v, s, v_0, a та t — це швидкість, відстань від початкової точки, початкова швидкість (тобто швидкість у початковій точці), прискорення та час, протягом якого об'єкт рухається в цьому напрямку, відповідно. Зверніть увагу, що їх можна спростити наступним чином:
v^2 - v^2_0= 2as
Коли об'єкт рухається по дузі, з прискоренням до центроїда, діють такі рівняння:
a =v^2/r
де v, a та r — це швидкість, прискорення та радіус дуги, відповідно. Зверніть увагу, що об'єкт не може змінити швидкість через критерії вашої екстрасенсорної здатності.
Вхідні дані
Вхідні дані мають наступний формат:
N a_maxx_{a,1} y_{a,1} x_{b,1} y_{b,1}x_{a,2} y_{a,2} x_{b,2} y_{b,2}...
N — це кількість відрізків; a_max — це максимальне прискорення, яке ви можете надати об'єкту; (x_{a,i}, y_{a,i}) та (x_{b,i}, y_{b,i}) — це початкова та кінцева точки i-го відрізка, відповідно. Заданий маршрут може мати перетини, але ви не можете змінити напрямок там.
Вхідні дані відповідають наступним обмеженням: 0 < N ≤ 40000, 1 ≤ a_max ≤ 100, та -100 ≤ x_ai, y_ai, x_bi, y_bi ≤ 100.
Вихідні дані
Виведіть мінімальний час для переміщення об'єкта з початкової точки до кінцевої точки з відносною або абсолютною похибкою не більше 10^{-6}. Ви можете вивести будь-яку кількість цифр після десяткової точки.