Water Falls |

Consider the set of line segments *P*1, *P*2 and *P*3 of figure 1,
representing the side view of a set of planes. What happens if
some water falls (in the vertical direction and ignoring
horizontal deviations created by kinetics) from source point *Sa*?
It flows over the plane *P*3, to *P*1, finally falling on the ground
at the point *Ga*. It is easy to see that, if the water is falling
from source point *Sb*, then it hits the ground at the point *Gb*.

Given a list of lines segments and a list of source points, the proposed problem is to determine the corresponding falling points on the ground. To simplify the problem, it is assumed that neither horizontal lines nor crossing lines are given. Also no coincidences exist in the vertical projection of all points (the x coordinates of the end points and of the source points are all different).

The input is a text file, containing several lines as follows.

The
first line of the input contains the number *NP* (integer format) of
line segments. It is followed by *NP* lines containing, each one,
the coordinates of the two end points of a segment, in the
sequence
*x*_{1} *y*_{1} *x*_{2} *y*_{2}, separated by single spaces. No order is
supposed, for this case, between point 1 and point 2 and numbers
are written in the integer format.

The next line is the number *NS*
(integer format) of source points. It is followed by *NS* lines
containing, each one, a pair of integer values *x* *y*, separated by a
single space, which are the coordinates of the corresponding
source point.

*NS* lines of text containing, each one, the coordinate *x* (integer
format) of the corresponding falling point *G*. The output values
must keep the input order.

1 4 14 7 3 4 11 13 16 11 1 10 6 7 2 1 4 3 3 10 4 14 14 2 13

10 16 2

**Note:** The picture below corresponds to the sample input.

A. Augusto Sousa, ACM-UP'2001