Description：

平面上有 $n$ 个点可以产生收益， $A$ 每次只能朝左，右，上，左上和右上五个方向走到最近的一个没有产生过收益的点停下来，问 $A$ 最多能得到多少收益， $B$ 要把所有可能在最优方案下的路径全部覆盖，每次纵坐标必须增大，问最少需要几次。

$1\leqslant n\leqslant 50000,$ 同一层的点不超过 $1000$ 个。

Solution：

第一问直接 $DP$ ，开一个桶记录上一个在 $x=k,y=x+k,y=-x+k$ 的点是哪一个就可以处理行与行之间的转移，行内的转移稍微有点复杂，如果从某个点进入从这个点离开，那么只能获得这个点的收益，因为根据题意不能两次到达同一个点，如果从另一个点离开，那么可以获得他们之间的以及左边或者右边的收益，画个图就是：

那么我们就从左往右扫一下再从右往左扫一下得到每个点左边或者右边的收益就行了。

因为要输出路径所以记一下转移倒序输出，

第二问有点复杂，首先我们需要知道哪些边可能在最优路径上，这个可以反着 $DP$ 一下得到，然后我们可以建出来一个转移图，要求的就是用最小的次数覆盖整个图，这个可以看成是一个有源汇有上下界最小流问题，可以先做一遍有源汇可行流，再减去残量网络上 $T$ 到 $S$ 得最大流即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 50010

struct point

{

	int x,y,id;

}p[MAXN];

map<int,int> bas1,bas2,bas3;

int b1[MAXN],b2[MAXN],b3[MAXN];

map<int,vector<point> > s;

#define iter vector<point>::iterator

#define INF 0x3f3f3f3f

int vall[MAXN],valr[MAXN],val[MAXN];

int lasl[MAXN],lasr[MAXN],las[MAXN];

int f[MAXN],pre[MAXN],pretag[MAXN];

bool vis[MAXN];

int ans = 0,st = 0x3f3f3f3f;

void print(int k)

{

	if(k == 0)return;

	if(pretag[k] == 0)

	{

		printf("%d ",k);

		print(pre[k]);

		return;

	}

	if(pretag[k] == -1)

	{

		int cur = k;

		while(lasl[cur] != 0)printf("%d ",cur),cur = lasl[cur];

		printf("%d ",cur);cur = lasr[k];

		while(cur != pre[k])printf("%d ",cur),cur = lasr[cur];

		printf("%d ",pre[k]);

		print(las[pre[k]]);

		return;

	}

	if(pretag[k] == 1)

	{

		int cur = k;

		while(lasr[cur] != 0)printf("%d ",cur),cur = lasr[cur];

		printf("%d ",cur);cur = lasl[k];

		while(cur != pre[k])printf("%d ",cur),cur = lasl[cur];

		printf("%d ",pre[k]);

		print(las[pre[k]]);

		return;

	}

	return;

}

bool cmp_x(point a,point b){return a.x < b.x;}

void solve1()

{

	for(int i = 1;i <= n;++i)s[-p[i].y].push_back(p[i]);

	for(map<int,vector<point> >::iterator k = s.begin();k != s.end();++k)

	{

		vector<point> t = k -> second;

		sort(t.begin(),t.end(),cmp_x);

		int last = 0;

		int siz = t.size() - 1;

		for(int i = 0;i <= siz;++i)vall[t[i].id] = 1 + vall[last],lasl[t[i].id] = last,last = t[i].id;

		last = 0;

		for(int i = siz;i >= 0;--i)valr[t[i].id] = 1 + valr[last],lasr[t[i].id] = last,last = t[i].id;

		for(int i = 0;i <= siz;++i)

		{

			b1[t[i].id] = bas1[t[i].x];b2[t[i].id] = bas2[t[i].y - t[i].x];b3[t[i].id] = bas3[t[i].y + t[i].x];

			if(f[b1[t[i].id]] > val[t[i].id])val[t[i].id] = f[b1[t[i].id]],las[t[i].id] = b1[t[i].id];

			if(f[b2[t[i].id]] > val[t[i].id])val[t[i].id] = f[b2[t[i].id]],las[t[i].id] = b2[t[i].id];

			if(f[b3[t[i].id]] > val[t[i].id])val[t[i].id] = f[b3[t[i].id]],las[t[i].id] = b3[t[i].id];

		}

		for(int i = 0;i <= siz;++i)

		{

			for(int j = 0;j <= siz;++j)

			{

				if(i == j)

				{

					if(val[t[i].id] + 1 > f[t[i].id])f[t[i].id] = val[t[i].id] + 1,pre[t[i].id] = las[t[i].id],pretag[t[i].id] = 0;

				}

				else

				{

					if(i < j && val[t[j].id] + vall[t[j].id] > f[t[i].id])f[t[i].id] = val[t[j].id] + vall[t[j].id],pre[t[i].id] = t[j].id,pretag[t[i].id] = -1;

					if(i > j && val[t[j].id] + valr[t[j].id] > f[t[i].id])f[t[i].id] = val[t[j].id] + valr[t[j].id],pre[t[i].id] = t[j].id,pretag[t[i].id] = 1;

				}

			}

		}

		for(int i = 0;i <= siz;++i)bas1[t[i].x] = bas2[t[i].y - t[i].x] = bas3[t[i].y + t[i].x] = t[i].id;

	}

	if(bas1[0] != 0 && f[bas1[0]] > ans || (f[bas1[0]] == ans && bas1[0] < st))ans = f[bas1[0]],st = bas1[0];

	if(bas2[0] != 0 && f[bas2[0]] > ans || (f[bas2[0]] == ans && bas2[0] < st))ans = f[bas2[0]],st = bas2[0];

	if(bas3[0] != 0 && f[bas3[0]] > ans || (f[bas3[0]] == ans && bas3[0] < st))ans = f[bas3[0]],st = bas3[0];

	cout << ans << endl;

	print(st);cout << endl;

	return;

}

vector<int> vec[MAXN];

bool added[MAXN];

bool valid[MAXN];

namespace FLOW

{

	int s,t;

	struct edge

	{

		int to,nxt,f;

	}e[MAXN * 20];

	int edgenum = 0;

	int lin[MAXN];

	void add(int a,int b,int f)

	{

		e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

		e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

		return;

	}

	int ind[MAXN];

	void adde(int a,int b,int l)

	{//if(l == 1)cout << a << " " << b << endl;

		add(a,b,INF - l);

		ind[a] -= l;ind[b] += l;

		return;

	}

	int S,T;

	int ch[MAXN];

	int head[MAXN];

	bool BFS()

	{

		queue<int> q;q.push(S);

		memset(ch,-1,sizeof(ch));ch[S] = 0;

		while(!q.empty())

		{

			int k = q.front();q.pop();

			for(int i = lin[k];i != -1;i = e[i].nxt)

			{

				if(ch[e[i].to] == -1 && e[i].f)

				{

					ch[e[i].to] = ch[k] + 1;

					q.push(e[i].to);

				}

			}

		}

		return (ch[T] != -1);

	}

	int flow(int k,int f)

	{

		if(k == T)return f;

		int r = 0;

		for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

		{

			if(ch[e[i].to] == ch[k] + 1 && e[i].f)

			{

				int l = flow(e[i].to,min(f - r,e[i].f));

				e[i].f -= l;r += l;e[i ^ 1].f += l;

			}

			lin[k] = i;

		}

		if(r == 0)ch[k] = -1;

		return r;

	}

	long long dinic()

	{

		long long ans = 0,r;

		memcpy(head,lin,sizeof(lin));

		while(BFS())

		{

			int r = flow(S,INF);

			ans += r;

			memcpy(lin,head,sizeof(lin));

		}

		return ans;

	}

	int calc()

	{

		S = t + 1;T = S + 1;

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

		{

			if(ind[i] < 0)add(i,T,-ind[i]);

			if(ind[i] > 0)add(S,i,ind[i]);

		}

		dinic();

		add(t,s,INF);

		return dinic();

	}

}

void solve2()

{

	memset(FLOW::lin,-1,sizeof(FLOW::lin));

	s.clear();

	for(int i = 1;i <= n;++i)s[p[i].y].push_back(p[i]);

	FLOW::s = n + 1;FLOW::t = n + 2; 

	if(f[bas1[0]] == ans)FLOW::adde(FLOW::s,bas1[0],1),valid[bas1[0]] = true;

	if(f[bas2[0]] == ans)FLOW::adde(FLOW::s,bas2[0],1),valid[bas2[0]] = true;

	if(f[bas3[0]] == ans)FLOW::adde(FLOW::s,bas3[0],1),valid[bas3[0]] = true;

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

	{

		if(!valid[i])FLOW::adde(FLOW::s,i,0);

		FLOW::adde(i,FLOW::t,0);

	}

	for(map<int,vector<point> >::iterator it = s.begin();it != s.end();++it)

	{

		vector<point> t = it -> second;//cout << it -> first << endl;

		//cout << " : ";for(vector<point>::iterator ii = t.begin();ii != t.end();++ii)cout << ii -> id << " ";cout << endl;

		//cout << " : ";for(vector<point>::iterator ii = t.begin();ii != t.end();++ii)cout << f[ii -> id] << " ";cout << endl;

		sort(t.begin(),t.end(),cmp_x);

		int siz = t.size() - 1;

		for(int i = 0;i <= siz;++i)

		{

			if(!valid[t[i].id])continue;

			for(int j = 0;j <= siz;++j)

			{

				int x = t[i].id,y = t[j].id;

				if(i == j)

				{

					if(val[t[i].id] + 1 == f[t[i].id] && !added[x])

					{

						if(b1[x] != 0 && f[b1[x]] == val[x])FLOW::adde(x,b1[x],1),valid[b1[x]] = true;

						if(b2[x] != 0 && f[b2[x]] == val[x])FLOW::adde(x,b2[x],1),valid[b2[x]] = true;

						if(b3[x] != 0 && f[b3[x]] == val[x])FLOW::adde(x,b3[x],1),valid[b3[x]] = true;

						added[x] = true;

					}

				}

				else

				{

					if(((i < j && val[y] + vall[y] == f[x]) || (i > j && val[y] + valr[y] == f[x])) && !added[y])

					{

						if(b1[y] != 0 && f[b1[y]] == val[y])FLOW::adde(y,b1[y],1),valid[b1[y]] = true;

						if(b2[y] != 0 && f[b2[y]] == val[y])FLOW::adde(y,b2[y],1),valid[b2[y]] = true;

						if(b3[y] != 0 && f[b3[y]] == val[y])FLOW::adde(y,b3[y],1),valid[b3[y]] = true;

						added[y] = true;

					}

				}

			}

		}

	}

	cout << FLOW::calc() << endl;

	return;

}

int main()

{

	scanf("%d",&n);

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

	{

		p[i].x = rd();

		p[i].y = rd();

		p[i].id = i;

	}

	solve1();

	solve2();

	return 0;

}