Чарли Жук-Майский
Чарли умеет летать. Однако каждый раз, когда он хочет переместиться из одной точки в другую, это становится для него сложной задачей. Основная проблема в том, что Чарли — майский жук. Как известно, все майские жуки (не путать с тараканами) неуклюжи и медлительны. Им требуется время не только для полета по прямой, но и для выполнения поворотов. Учитывая эти ограничения, сможете ли вы помочь Чарли найти самый быстрый маршрут?
Входные данные
Входные данные состоят из нескольких наборов. Первая строка каждого набора содержит целые числа N, S и T (1 ≤ N ≤ 1000, 1 ≤ S, T ≤ 1000), где N — количество прямых траекторий полета майского жука (также известных как "майкоридоры"), S — скорость Чарли в метрах в секунду, а T — скорость его поворота в градусах в секунду. Вторая строка содержит шесть целых чисел (0 ≤ X_f, Y_f, Z_f, X_t, Y_t, Z_t ≤ 10000), указывающих начальную точку (X_f, Y_f, Z_f) и пункт назначения (X_t, Y_t, Z_t).
Каждая из следующих N строк содержит шесть целых чисел 0 ≤ X_1, Y_1, Z_1, X_2, Y_2, Z_2 ≤ 10000, указывающих, что существует отрезок (майкоридор), соединяющий точки (X_1, Y_1, Z_1) с (X_2, Y_2, Z_2). Гарантируется, что ни одна внутренняя точка отрезка не является концом другого отрезка, и что как начальная, так и конечная позиции являются концами хотя бы одного из отрезков. Все координаты заданы в метрах.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую одно вещественное число R, обозначающее минимальное время, которое потребуется Чарли, чтобы добраться от начальной до конечной точки. Чарли может двигаться только по целым прямым отрезкам, все они могут использоваться в обоих направлениях. Время для любого такого пути равно R = L/S + D/T секунд, где L — сумма длин всех пройденных отрезков (в метрах), а D — сумма углов, необходимых для поворота между последовательными отрезками (в градусах). Вы можете выбрать начальное и конечное направление, в котором смотрит Чарли, и предположить, что всегда существует хотя бы один путь от начальной до конечной точки.
Ответ будет принят как правильный, если разница между R и ответом, вычисленным судьями, не превышает 0.001.