题目描述
有N(1<=N<=100,000)座小山,每座山所占的区域用直线(x1,y1)到 (x2,y2)来表示(x1<x2并且 y1<y2)。也就是说这些山用笛卡尔坐标系里的线段来表示, 这些用于表示小山的线段都没有任何交点,第一座山的一端位于(x1,y1)=(0,0)
贝西从(0,0)开始在第一座山上漫步,一旦贝西到了一座山,她会一直走到该山的终点,这时,她会从边缘处起跳,如果她降落到另一座山上,她会继续在新的山上漫步。贝西起跳后沿y轴方向下落 ,如果贝西不能降落到一座山上,她会一直下落,直到到达y轴的负无穷大位置(y=−infinity)。
每座用线段表示的山 (x1,y1)−>(x2,y2)包含(x1,y1)这个点,但不包含(x2,y2),请计算出贝西总共在多少座山上漫步了。
输入格式
第 1行:丘陵数,N。
第 2..1+N行:第 i+1行包含四个整数 (x1,y1,x2,y2)
描述山 i。每个整数都在范围内
0..1,000,000,000.
输出格式
第 1行:Bessie在旅途中触及的山丘数量。
样例
输入样例
4
0 0 5 6
1 0 2 1
7 2 8 5
3 0 7 7
输出样例
3
提示
有四座山。第一个山丘从 (0,0)延伸到 (5,6),依此类推。
Bessie在 1、4和最后 3山上行走。