Description：

给定二维直角坐标系。我们要求一条折线只能从左边到右边一笔画过去，并且折线的每一段和x轴的夹角在 $[-45^\circ,45^\circ]$ 之间。给定坐标系上的n个格点，问最少需要画多少条平直折线才能覆盖所有的点。

$1\leqslant n \leqslant30000 $

Solution：

像新打鼹鼠那题一样，先变换一下坐标系，把它变成 $(-x-y,x-y)$ ，那么就变成了一个点右上角的所有区域，按 $x$ 排序后就变成了用最少的单调下降子序列覆盖所有 $y$ 坐标，由 $\text{Dillworth}$ 定理得最小链覆盖 $=$ 最长反链覆盖，于是求 $y$ 坐标的最长上升子序列即可。

排序的时候一定不要忘了 $y$ ！！！

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n;

#define MAXN 30010

map<int,int> s;

int tot = 0;

struct point

{

	int x,y;

}p[MAXN];

int by[MAXN];

bool cmp_x(point a,point b){return (a.x == b.x ? a.y > b.y : a.x < b.x);}

int lowbit(int x){return x & (-x);}

int c[MAXN];

void add(int p,int x){for(int i = p;i <= tot;i += lowbit(i))c[i] = max(c[i],x);}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res = max(res,c[i]);return res;}

int main()

{

	scanf("%d",&n);

	int x,y;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&x,&y);

		p[i].x = -x - y;p[i].y = x - y;

		by[i] = p[i].y;

	}

	sort(p + 1,p + 1 + n,cmp_x);

	sort(by + 1,by + 1 + n);

	for(int i = 1;i <= n;++i)

		if(i == 1 || by[i] != by[i - 1])

			s[by[i]] = ++tot;

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		int k = query(s[p[i].y] - 1);

		ans = max(ans,k + 1);

		add(s[p[i].y],k + 1);

	}

	cout << ans << endl;

	return 0;

}