6924: BZOJ2924:[Poi1998]Flat broken lines
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
给定二维直角坐标系。我们要求一条折线只能从左边到右边一笔画过去,并且折线的每一段和x轴的夹角在[-15°, 15°]之间。一条满足上述要求的折线被称为:平直折线。
给定坐标系上的n个格点,最少需要画多少条平直折线才能覆盖所有的点呢?
例如:
<img src="http://main.edu.pl/en/images/OI5/lam.gif" alt="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
提示
没有写明提示
题目来源
没有写明来源