#P3081. Bessie's Hill Hopping
Bessie's Hill Hopping
Bessie's Hill Hopping
There are \(N\) hills (\(1 \le N \le 10^5\)). Each hill is represented as a line segment from \((x_1, y_1)\) to \((x_2, y_2)\) with \(x_1 < x_2\) and \(y_1 < y_2\). The segments do not intersect or touch, even at endpoints; moreover, the first hill has one endpoint exactly at \((0, 0)\).
Bessie the cow starts her journey at \((0, 0)\) on the first hill. While on a hill, she walks to its endpoint \((x_2, y_2)\) and then jumps vertically downward (i.e. following the line \(x = x_2\)). If she lands on another hill, she continues walking on that hill. A hill represented by the segment from \((x_1, y_1)\) to \((x_2, y_2)\) is considered to contain the point \((x_1, y_1)\) but not \((x_2, y_2)\). That is, if Bessie falls along \(x=x_1\) onto the hill, she will land on it, but if she falls onto \(x=x_2\) she will miss it. If Bessie does not land on any hill, she continues falling infinitely downwards.
Calculate the total number of hills that Bessie touches during her journey.
inputFormat
The first line contains an integer \(N\) representing the number of hills. Each of the following \(N\) lines contains four integers \(x_1\), \(y_1\), \(x_2\), and \(y_2\), describing a hill.
You can assume that the segments do not intersect, and the first hill has \((x_1, y_1) = (0, 0)\).
outputFormat
Output a single integer representing the total number of hills that Bessie touches.
sample
1
0 0 1 1
1
</p>