eolymp
bolt
Try our new interface for solving problems
Problems

Pythagoraslope

Pythagoraslope

Alice, your girlfriend, is a student at an art school. She is in the final year, and now working hard to build a facture for fulfilling the requirement to graduate. Her work is a large pinball with many straight slopes. Before starting to build, she has made several plans, but is unsure if they work as expected. So she asked you, a professional programmer, for help. You have modeled this situation by a two dimensional plane with some line segments on it. In this model, there is gravitation downward, i.e., in the decreasing direction of \textbf{y}-coordinate. Your task is to write a program that simulates the pinball, and compute the last position where the ball crosses the \textbf{x}-axis. You may assume coefficient of restitution between the slopes and the ball is \textbf{0}, i.e., when the ball collides a slope, it instantly loses the velocity component orthogonal to the slope. And since her pinball is so large, you may also assume that the volume of the ball is negligible. \InputFile The input consists of multiple data sets. Each data set is given in the format below. \textbf{N} \textbf{g} \textbf{x y} \textbf{x_\{1,1\} y_\{1,1\} x_\{1,2\} y_\{1,2\}} \textbf{. . .} \textbf{x_\{N,1\} y_\{N,1\} x_\{N,2\} y_\{N,2\}} where \textbf{N} (\textbf{N} ≤ \textbf{100}) is the number of slopes, \textbf{g} is gravity acceleration, and (\textbf{x}, \textbf{y}) is the initial position of the ball. Each of the following \textbf{N} lines represents a slope, which is a line segment between (\textbf{x_\{i,1\}}, \textbf{y_\{i,1\}}) and (\textbf{x_\{i,2\}}, \textbf{y_\{i,2\}}). You may assume that: \begin{itemize} \item all coordinates are more than or equal to \textbf{1}, and less than or equal to \textbf{10000}; \item \textbf{x_\{i,1\}} ≠ \textbf{x_\{i,2\}} and \textbf{y_\{i,1\}} ≠ \textbf{y_\{i,2\}} for all \textbf{1} ≤ \textbf{i} ≤ \textbf{N}; \item no two line segments cross each other; \item extending or shrinking a slope by the length of \textbf{0.0001} does not change the ball’s trail, that is, do not change the set of slopes where the ball passes; \item the ball never collides to a slope at the angle of \textbf{90 ± 0.0001} degrees from the slope; and \item the initial position of the ball never lies on any slope. \end{itemize} The end of the input is indicated by a line containing a single zero. This is not a part of the data sets, and you must not process it. \OutputFile For each data set, output the \textbf{x}-coordinate of the final crossing point of the ball’s trail and the \textbf{x}-axis. Your program may print any number of digits after the decimal point, but the output must not contain an error greater than \textbf{10^\{−4\}} ( = \textbf{0.0001}).
Time limit 1 second
Memory limit 64 MiB
Input example #1
3
1
120 1000
100 100 180 20
170 10 270 30
270 40 400 20
0
Output example #1
403.87458314
Source ACM-ICPC Japan Alumni Group Summer Camp 2007, Day 2, Tokyo, Japan, 2007-09-23