P1766 Liquid Droplet

In the plane, there are several line segments $L_i$ (not necessarily pairwise disjoint) that form one track after another. A droplet of liquid falls from above. If it encounters a track, it slides downward along the track and leaves the track from its lower end; while on a track, it is not affected by anything else. Otherwise, it falls straight down vertically. Determine the position from which the droplet finally exits the entire system. I'm sure this problem won't stump you.

The first line contains two integers $N$ and $S$, indicating there are $N$ segments, and the droplet starts falling from the position with x-coordinate $S$. Each of the following $N$ lines contains four integers $x_{i1}$, $y_{i1}$, $x_{i2}$, $y_{i2}$ describing the endpoints of each segment. Note that each segment excludes its two endpoints; the liquid can pass through an endpoint without touching the segment.

Output a single integer on one line: the final x-coordinate where the droplet falls out.

For $50\%$ of the testdata, $1\le N\le 100$, $|x|,|y|,|S| \le 500$. For $100\%$ of the testdata, $1\le N\le 10^5$, $|x|,|y|,|S| \le 10^9$.  Translated by ChatGPT 5