Description

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.

Input Format

• 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$.

Output Format

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

4 
0 0 5 6 
1 0 2 1 
7 2 8 5 
3 0 7 7 

3 

Hint

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