P3081 [USACO13MAR] Hill Walk G

题目描述

有 $N(1 \le N \le 10 ^ 5)$ 座小山,每座山所占的区域用直线 $(x1, y1)$ 到 $(x2, y2)$ 来表示($x1 < x2$ 并且 $y1 < y2$)。也就是说这些山用笛卡尔坐标系里的线段来表示,这些用于表示小山的线段都没有任何交点,第一座山的一端位于 $(x1, y1) = (0,0)$。 贝西从 $(0,0)$ 开始在第一座山上漫步,一旦贝西到了一座山,她会一直走到该山的终点,这时,她会从边缘处起跳,如果她降落到另一座山上,她会继续在新的山上漫步。贝西起跳后沿 $y$ 轴方向下落,如果贝西不能降落到一座山上,她会一直下落,直到到达 $y$ 轴的负无穷大位置($y = -\infin$)。 每座用线段表示的山 $(x1, y1) \to (x2, y2)$ 包含 $(x1, y1)$ 这个点,但不包含 $(x2, y2)$,请计算出贝西总共在多少座山上漫步了。

输入格式

第一行输入一个整数,表示山的数量 $N$。 第 $2 \sim N+1$ 行,第 $i+1$ 行包含四个整数 $(x_1, y_1, x_2, y_2)$,描述第 $i$ 座山。保证数据在 $[0, 10^9]$ 范围内。

输出格式

输出一个整数,表示 Bessie 全程到达的山的数量。

说明/提示

如输入所述,总共有 $4$ 座山。Bessie 的旅程经过了山 $1, 4, 3$。