eolymp
bolt
Try our new interface for solving problems
Problems

Sniper Shot

Sniper Shot

There is a sniper at point \textbf{S}. His mission is to eliminate an enemy of the state, who rides his bicycle along a straight line from point \textbf{A} to point \textbf{B}. The bullet flies along a striaght line with infinite speed. There are \textbf{n} rectangular parallelepiped-shaped skyscrapers in the city. The bullet can't fly through the skyscraper but can touch its border. Of course, the sniper will make a deadly shot as soon as possible. Your task is to calculate the coordinates of the enemy at the moment of the shot. \InputFile The first line contains space-separated coordinates of \textbf{S}: \textbf{s_x}, \textbf{s_y}, \textbf{s_z} (\textbf{s_z} ≥ \textbf{0}). The second line contains space-separated coordinates of points \textbf{A} and \textbf{B}: \textbf{a_x}, \textbf{a_y}, \textbf{b_x}, \textbf{b_y}. The enemy of the state moves on the surface of earth, so his \textbf{z}-coordinate is always equal to zero. The third line containts an integer \textbf{n} (\textbf{0} ≤ \textbf{n} ≤ \textbf{100}). Each of the following \textbf{n} lines contains space-separated numbers \textbf{l_x}, \textbf{l_y}, \textbf{r_x}, \textbf{r_y}, \textbf{h} (\textbf{l_x} < \textbf{r_x}; \textbf{l_y} < \textbf{r_y}; \textbf{h} > \textbf{0}) --- coordinates of the opposite corners of the bottom of the current skyscraper and its height. The sides of the skyscrapers are parallel to the corrdinate axes. All coordinates and heights are integers and don't exceed \textbf{100} by their absolute values. It is guaranteed that no two skyscrapers have common points, the point \textbf{S} doesn't lie inside or on the border of the skyscraper and the segment \textbf{AB} doesn't have common points with any of the skyscrapers. \OutputFile If the enemy of the state cannot be eliminated, output "\textbf{Impossible}". In the other case output the coordinates of the enemy of the state precise up to \textbf{10^\{−7\}}.
Time limit 1 second
Memory limit 16 MiB
Input example #1
0 0 2
-4 4 4 4
2
-3 2 -1 3 10
1 -1 4 2 20
Output example #1
-1.3333333333 4.0000000000
Author Alex Samsonov
Source Ural SU Contest. Petrozavodsk Winter Session, February 2009