eolymp
bolt
Try our new interface for solving problems
Məsələlər

Charlie the Cockchafer

Charlie the Cockchafer

\includegraphics{https://static.e-olymp.com/content/71/711e9e4ed526295715b03ec5b5c91642268132c4.jpg} Charlie knows how to fly. Despite this, whenever Charlie wants to move from one point to another, it becomes a tedious task for him. The main trouble is that Charlie is a cockchafer. And it is a well-known fact that all cockchafers (do not confuse them with cockroaches) are clumsy and slow. Not only they need some time to fly along a straight line, they also spend more time making turns. Knowing their limitations, will you help Charlie to find the quickest route? \InputFile The input consists of several instances. The first line of each instance contains integers \textbf{N}, \textbf{S} and \textbf{T} (\textbf{1} ≤ \textbf{N} ≤ \textbf{1000},\textbf{1} ≤ \textbf{S}, \textbf{T} ≤ \textbf{1000}), where \textbf{N} is the number of straight cockchafer flight trajectories (also known as "cockridors"), \textbf{S} is Charlie’s speed in meters per second, and \textbf{T} is the speed of him turning in degrees per second. The second line contains six integers (\textbf{0} ≤ \textbf{X_f}, \textbf{Y_f}, \textbf{Z_f}, \textbf{X_t}, \textbf{Y_t}, \textbf{Z_t} ≤ \textbf{10000}) indicating the starting point (\textbf{X_f}, \textbf{Y_f}, \textbf{Z_f}) and the destination (\textbf{X_t}, \textbf{Y_t}, \textbf{Z_t}). Each of the following \textbf{N} lines contains six integers \textbf{0} ≤ \textbf{X_1}, \textbf{Y_1}, \textbf{Z_1}, \textbf{X_2}, \textbf{Y_2}, \textbf{Z_2} ≤ \textbf{10000} stating there is a line segment (cockridor) joining points (\textbf{X_1}, \textbf{Y_1}, \textbf{Z_1}) with (\textbf{X_2}, \textbf{Y_2}, \textbf{Z_2}). You are guar-anteed that no internal point of the segment is an endpoint of another segment, and that both the initial and the final positions are endpoints of at least one of the segments. All coordinates are given in meters. \OutputFile For each input instance, print a single line containing one real number \textbf{R}, giving the shortest time Charlie needs to get from the initial to the final point. Charlie can only move along the whole straight segments, all of them can be used in both directions. The time for any such path is \textbf{R = L/S + D/T} seconds, where \textbf{L} is the sum of the lengths of all segments traversed (in meters) and \textbf{D} is the sum of the angles needed to turn between consecutive segments (in degrees). You can choose the initial and final direction that Charlie is facing, and assume that there always exists at least one path from the initial to the final point. The answer will be accepted as correct if the difference between \textbf{R} and the answer computed by the judges is at most \textbf{0.001}.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
1 3 1
0 0 0 10 10 10
0 0 0 10 10 10
2 3 1
0 0 0 10 10 10
0 0 0 0 10 10
10 10 10 0 10 10
Çıxış verilənləri #1
5.7735
98.0474