2924 - [Poi1998]Flat broken lines

给定二维直角坐标系。我们要求一条折线只能从左边到右边一笔画过去,并且折线的每一段和x轴的夹角在[-15°, 15°]之间。一条满足上述要求的折线被称为:平直折线。 给定坐标系上的n个格点,最少需要画多少条平直折线才能覆盖所有的点呢? 例如: example 上图有6个点:(1, 6), (10, 8), (1, 5), (2, 20), (4, 4), (6, 2),最少需要3条平直折线。

输入

第一行,1个正整数:点数n (<= 30000) 下面n行:坐标(x, y) ,(0 <= x, y <= 30000)

输出

最少需要多少条平直折线

样例

输入

6
1 6
10 8
1 5
2 20
4 4
6 2

输出

3
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题