#2136. Hill Walk

Hill Walk

题目描述

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

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

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

输入格式

1\red{1 }行:丘陵数,N\red{N}

2..1+N\red{2..1+N }行:第 i+1\red{i+1 }行包含四个整数 (x1,y1,x2,y2)\red{(x1,y1,x2,y2)}

描述山 i\red{i}。每个整数都在范围内

0..1,000,000,000.\red{0..1,000,000,000.}

输出格式

1\red{1 }行:Bessie\red{Bessie }在旅途中触及的山丘数量。

样例

输入样例

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

输出样例

3

提示

有四座山。第一个山丘从 (0,0)\red{(0,0) }延伸到 (5,6)\red{(5,6),}依此类推。

Bessie\red{Bessie }1\red{1}4\red{4 }和最后 3\red{3 }山上行走。