#P3081. [USACO13MAR] Hill Walk G

[USACO13MAR] Hill Walk G

说明

N(1N105)N(1 \le N \le 10 ^ 5) 座小山,每座山所占的区域用直线 (x1,y1)(x1, y1)(x2,y2)(x2, y2) 来表示(x1<x2x1 < x2 并且 y1<y2y1 < y2)。也就是说这些山用笛卡尔坐标系里的线段来表示,这些用于表示小山的线段都没有任何交点,第一座山的一端位于 (x1,y1)=(0,0)(x1, y1) = (0,0)

贝西从 (0,0)(0,0) 开始在第一座山上漫步,一旦贝西到了一座山,她会一直走到该山的终点,这时,她会从边缘处起跳,如果她降落到另一座山上,她会继续在新的山上漫步。贝西起跳后沿 yy 轴方向下落,如果贝西不能降落到一座山上,她会一直下落,直到到达 yy 轴的负无穷大位置(y=y = -\infin)。

每座用线段表示的山 (x1,y1)(x2,y2)(x1, y1) \to (x2, y2) 包含 (x1,y1)(x1, y1) 这个点,但不包含 (x2,y2)(x2, y2),请计算出贝西总共在多少座山上漫步了。

输入格式

第一行输入一个整数,表示山的数量 NN

2N+12 \sim N+1 行,第 i+1i+1 行包含四个整数 (x1,y1,x2,y2)(x_1, y_1, x_2, y_2),描述第 ii 座山。保证数据在 [0,109][0, 10^9] 范围内。

输出格式

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

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

3 

提示

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