eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Parabolic teleports

Parabolic teleports

Flatland is a plane with a Cartesian coordinate system \textbf{Oxy}. Citizens of Flatland are points that move with the speed\textbf{1}. Consequently, the minimal time it takes for a Flatlander to move from point \textbf{V} to point \textbf{W} is equal to the length of the line segment \textbf{VW}. This fact is taught in the schools of Flatland as the "shortest path theorem". However, since George Edward Nius invented the devices called \textit{parabolic teleports}, the theorem no longer holds. A parabolic teleport is a contiguous section of a parabola along which it is possible to move with infinite speed. In other words, it is possible to move from any point on the parabolic teleport to any other point on the same parabolic teleport in zero time. The points (\textbf{x}, \textbf{y}) that belong to the teleport are given by the formulae \textbf{y = A—x^2+B—x+C}, \textbf{XL} ≤ \textbf{x} ≤ \textbf{XR}, where \textbf{A}, \textbf{B}, \textbf{C}, \textbf{XL}, \textbf{XR} are the parameters of the teleport. After inventing the teleports, G.E.Nius founded a company to build them. At the moment, the company has already built \textbf{N} of those devices. One might imagine that they are shoveling money left and right, but… But in practice, the Flatlanders still think the shortest path theorem is true and nobody has even tried the parabolic teleports. To help the situation, G.E.Nius has hired you to write a program that, given two points \textbf{V} and \textbf{W}, would compute the time it would take to move from \textbf{V} to \textbf{W} using the teleports the company has already built. The idea is that the users of the program will see that the time is less than the length of the segment \textbf{VW} and start to use the invention of Mr. Nius. Are you up to the task? \InputFile Input data are in the first line of the file is the integer \textbf{N} (\textbf{0} ≤ \textbf{N} ≤ \textbf{100}), the number of the teleports. On the second line of the file are the integers \textbf{X_V} and \textbf{Y_V} (\textbf{-100} ≤ \textbf{X_V} ≤ \textbf{100}, \textbf{-1000000} ≤ \textbf{Y_V} ≤ \textbf{1000000}), the coordinates of the source point \textbf{V}. On the third line of the file are the integers \textbf{X_W} and \textbf{Y_W} (\textbf{-100} ≤ \textbf{X_W} ≤ \textbf{100}, \textbf{-1000000} ≤ \textbf{Y_W} ≤ \textbf{1000000}), the coordinates of the destination point \textbf{W}. Each of the \textbf{N} following lines contains \textbf{5} integers, separated by spaces, that describe the ith teleport -- giving its parameters \textbf{A_i}, \textbf{B_i}, \textbf{C_i}, \textbf{X_Li}, \textbf{X_Ri} (\textbf{-100} ≤ \textbf{A_i}, \textbf{B_i}, \textbf{C_i} ≤ \textbf{100}, \textbf{A_i} ≠ \textbf{0}, \textbf{-100} ≤ \textbf{X_Li} < \textbf{X_Ri} ≤ \textbf{100}). \OutputFile Output data should be put to the first and only line of the file should contain one real number, the minimal time it takes to move from point \textbf{A} to point \textbf{B}. The absolute error of the answer must not exceed \textbf{10^\{-4\}}.
Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
2
0 10
0 -10
1 0 0 -10 10
-1 0 0 -10 10
Выходные данные #1
6.2449979984
Источник ACM Programming Contest 2005, Minsk, October 2005