P3081 [USACO13MAR] Hill Walk G

There are $N$ hills ($1 \le N \le 10^5$). Each hill is a line segment from $(x1, y1)$ to $(x2, y2)$ with $x1 < x2$ and $y1 < y2$. No two segments intersect or touch, even at their endpoints. The first hill satisfies $(x1, y1) = (0, 0)$. Bessie the cow starts at $(0, 0)$ on the first hill. While on a hill, she climbs up until she reaches the end, then she jumps off the edge. She falls straight down at a fixed $x$. If she lands on another hill, she continues walking on that hill; otherwise, she keeps falling until she lands safely at $y = -\infty$. Each hill $(x1, y1) \to (x2, y2)$ contains the point $(x1, y1)$ but does not contain the point $(x2, y2)$. Therefore, Bessie will land on the hill if she falls on it from above at $x = x1$, but she will not land on the hill if she falls on it from above at $x = x2$. Please count the total number of hills that Bessie touches at some point during her walk.

* Line 1: The number of hills, $N$. * Lines 2..$1+N$: Line $i+1$ contains four integers $(x1, y1, x2, y2)$ describing hill $i$. Each integer is in the range $0..1{,}000{,}000{,}000$.

* Line 1: The number of hills Bessie touches on her journey.

There are four hills. The first hill runs from $(0, 0)$ to $(5, 6)$, and so on. Bessie walks on hills #1, #4, and finally #3. Translated by ChatGPT 5