jzoj 3833. 平坦的折线（lam）

jzoj 3833. 平坦的折线（lam）

Description
现在我们在一张纸上有一个笛卡尔坐标系。我们考虑在这张纸上用铅笔从左到右画的折线。我们要求任何两个点之间连接的直线段与x轴的夹角在-45~45之间，一条满足以上条件的折线称之为平坦的折线。假定给出了n个不同的整点（坐标为整数的点），最少用几条平坦的折线可以覆盖所有的点？

例子：

图中有6个整点：(1,6), (10,8), (1,5), (2,20), (4,4), (6,2)，要覆盖它们至少要3条平坦的折线。

任务：
写一个程序：
从文件lam.in中读入点的个数以及它们的坐标。
计算最少需要的折线个数。
将结果写入文件lam.out。

Input
在输入文件lam.in的第一行有一个正整数n，不超过30000，代表点的个数。接下来的n行表示这些点的坐标，每行有两个用一个空格隔开的整数x,y，0 <= x <= 30000, 0 <= y <= 30000。第i+1行的数字代表第i个点的坐标。

Output
在输出文件lam.out的第一行应当有且仅有一个整数——表示覆盖所有的点最少需要的折线数。

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

Sample Output
3

Data Constraint
数据规模
对于20%的数据，有N<=15。
对于100%的数据如题目。

题目大意：

求最少要几个与x轴的夹角在-45~45度的折线，覆盖所有的点。

题解：

与x轴的夹角在-45~45度这个条件很难处理，考虑将其逆时针转45度，x’=x-y，y’=x+y

原来：

转化成：

这样条件变成只要使线段不下降(斜率大于0)就行了，
将新的坐标按x为第一关键字，y为第二从小到大排序，
条件又变成只用使y坐标不下降
问题就变成同导弹拦截(NOIP1999)一样，求用多少个不下降序列覆盖完所有点
答案即为最长下降序列的长度(因为最长下降序列的每个点都可以做一个不下降序列的起点)

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 30005
#define Max 9999999997
using