8414: Hill Walk

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

有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) ,请计算出贝西总共在多少座山上漫步了。

输入格式

* Line 1: The number of hills, N.

* Lines 2..1+N: Line i+1 contains four integers (x1,y1,x2,y2)

describing hill i. Each integer is in the range

0..1,000,000,000.

输出格式

* Line 1: The number of hills Bessie touches on her journey.

输入样例 复制

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

输出样例 复制

3 

数据范围与提示

There are four hills. The first hill runs from (0,0) to (5,6), and so on.

Bessie walks on hills #1, #4, and finally #3.