Problem H

Image from Florence Ivy

Maria is quite addicted to pinball. She can shoot the ball to any position at the top of the board, but she cannot predict where the ball will end when it falls down, because it hits many bumpers on its way down.

She decided to model the pinball table as line segments and assume that the ball is a point that falls from infinite height. The ball falls straight vertically unless there is a segment immediately below it, in which case it follows the direction of the segment downwards until its end.

As you would expect the segments are closed, that is an endpoint is part of its segment. Pairs of segments do not intersect, not even at endpoints, and none is vertical or horizontal. Segments are not given in any specific order.


The first line contains an integer $N$ ($0\leq N \leq 100\, 000$), the number of segments. Then $N$ lines follow, each with four integers $x_1$ $y_1$ $x_2$ $y_2$, the coordinates of a segment ($-1\, 000\, 000 \leq x_ i,y_ i \leq 1\, 000\, 000$). The last line contains an integer $x_0$ ($-1\, 000\, 000 \leq x_0 \leq 1\, 000\, 000$), the initial $x$-coordinate of the ball.


Output a single integer $x_ T$, the final $x$-coordinate of the ball.

\includegraphics[width=0.2\textwidth ]{sample}
Figure 1: Sample input 1
\includegraphics[width=0.2\textwidth ]{sample2}
Figure 2: Sample input 2
Sample Input 1 Sample Output 1
-1 1 1 -1
1 -2 2 -3
Sample Input 2 Sample Output 2
-1 1 1 -1
1 -2 0 -3
1 -3 2 -4

Please log in to submit a solution to this problem

Log in