bzoj#P3076. [Usaco2013]Hill Walk

[Usaco2013]Hill Walk

题目描述

贝茜要爬山,每一段山路都可以抽象成一个线段,其两个端点分别为 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2)(x1<x2,y1<y2)(x_1<x_2,y_1<y_2),但是 (x2,y2)(x_2,y_2) 这个点是空的。题目保证任意两条线段都不交叉、相交(甚至在端点),并保证第一端山路的起点 (x1,y1)(x_1,y_1) 必然是 (0,0)(0,0)。现在贝茜要从原点开始爬,对于每一段山路都会从起点爬到终点。到了终点 (x2,y2)(x_2,y_2) 时,就会笔直地往下跳(即 yy 不断减小,xx 不变),直到落到下一端山路上。若贝茜会掉到 y=y=-\infty,则爬山结束。现在 FJ 给出了所有 山路的状况,贝茜想知道她能爬几段山路。

输入格式

第一行输入一个整数 nn,表示山路数量。

接下来 nn 行,每行输入四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,意义与题目中相同。

输出格式

一行一个整数表示答案。

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

数据规模与约定

对于 100%100\% 的数据,1n1051\le n\le 10^50x1,y1,x2,y21090\le x_1,y_1,x_2,y_2\le 10^9

提示

对于样例:

pic1