#P5487. Hill Walk

Hill Walk

题目描述

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

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

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

输入格式

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

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

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

0..1,000,000,000.{0..1,000,000,000.}

输出格式

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

样例

输入样例

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

输出样例

3

提示

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

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