一看上去就是一个二合一的题。那么先解决第一部分求最优路线（及所有可能在最优路线上的线段）。
由于不能往下走，可以以y坐标作为阶段。对于y坐标不同的点，我们将可以直接到达的两点连边，显然这样的边的个数是线性的。如果是右上方向那么横纵坐标差相等，左上则和相等，可以直接排序搞定。
y坐标相同的点（下称一排），如果某个靠左的点向靠右的点转移，那么这个靠右的点的左边所有点都可以走到。可以先将这一排点用之前的点更新完毕，求出某个点不往左右走的最大值，然后用左边的更新右边，右边的更新左边，每次记录一下最大值就是线性的了。于是整个dp一发就好了。
打印任意一种方案很简单。至于所有方案的路径并，可以把之前求出的“某个点不往左右走能得到的最大值”记录下来。从后往前，对于每一排，先找出“哪些点可以作为最优方案中该排最后一个到达的点”。然后再根据“某个点不往左右走能得到的最大值”找出“哪些点可以作为最优方案中该排第一个到达的点”，具体做法仍然可以先看左边再看右边。而根据这些点上一次的转移，就可以知道哪些线段可以在最优方案内，并且可以标记上之前的“哪些点可以作为最优方案中该排最后一个到达的点”，总的仍是线性。
做完之后进入第二部分。这部分比较明显，就是多源多汇的上下界最小流。新建一个超源超汇跑一发就做完了。开始跑了一个啥都不是的玩意拿了65分，数据水到一个境界了。
似乎不是很难。然而……太码农了……
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 50010
#define S 50001
#define T 50002
#define SS 50003
#define ST 50004
int n,from[N][],f[N],g[N],h[N],ans[N],pre[N],t=-;
int p[N],cur[N],d[N],q[N],degree[N],tot=;
struct data{int to,nxt,cap,flow;
}edge[N<<];
bool flag[N],tagend[N],tagstart[N];
struct point{int x,y,i,j;
}a[N];
void addedge(int x,int y,int z)
{
t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].cap=z,edge[t].flow=,p[x]=t;
t++;edge[t].to=x,edge[t].nxt=p[y],edge[t].cap=,edge[t].flow=,p[y]=t;
}
bool cmp(const point&a,const point&b)
{
return a.y<b.y||a.y==b.y&&a.x<b.x;
}
bool cmp2(const point&a,const point&b)
{
return a.y-a.x<b.y-b.x||a.y-a.x==b.y-b.x&&a.y<b.y;
}
bool cmp3(const point&a,const point&b)
{
return a.x+a.y<b.x+b.y||a.x+a.y==b.x+b.y&&a.y<b.y;
}
bool cmp4(const point&a,const point&b)
{
return a.x<b.x||a.x==b.x&&a.y<b.y;
}
void print(int x)
{
if (x==) return;
if (a[pre[x]].y==a[x].y)
{
print(pre[pre[x]]);
if (pre[x]>x)
{
printf("%d ",a[pre[x]].j);
int i=pre[x];
while (a[i+].y==a[i].y) i++,printf("%d ",a[i].j);
for (i=pre[x]-;i>=x;i--) printf("%d ",a[i].j);
}
else
{
printf("%d ",a[pre[x]].j);
int i=pre[x];
while (a[i-].y==a[i].y) i--,printf("%d ",a[i].j);
for (i=pre[x]+;i<=x;i++) printf("%d ",a[i].j);
}
}
else
{
print(pre[x]);
printf("%d ",a[x].j);
}
}
bool bfs(int s,int t)
{
memset(d,,sizeof(d));d[s]=;
int head=,tail=;q[]=s;
do
{
int x=q[++head];
for (int i=p[x];~i;i=edge[i].nxt)
if (d[edge[i].to]==-&&edge[i].flow<edge[i].cap)
{
d[edge[i].to]=d[x]+;
q[++tail]=edge[i].to;
}
}while (head<tail);
return ~d[t];
}
int work(int k,int f,int t)
{
if (k==t) return f;
int used=;
for (int i=cur[k];~i;i=edge[i].nxt)
if (d[k]+==d[edge[i].to])
{
int w=work(edge[i].to,min(f-used,edge[i].cap-edge[i].flow),t);
edge[i].flow+=w,edge[i^].flow-=w;
if (edge[i].flow<edge[i].cap) cur[k]=i;
used+=w;if (used==f) return f;
}
if (used==) d[k]=-;
return used;
}
void dinic(int s,int t)
{
while (bfs(s,t))
{
memcpy(cur,p,sizeof(p));
tot+=work(s,N,t);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj4200.in","r",stdin);
freopen("bzoj4200.out","w",stdout);
const char LL[]="%I64d";
#else
const char LL[]="%lld";
#endif
n=read();
for (int i=;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].j=i;
sort(a+,a+n+,cmp);
for (int i=;i<=n;i++) a[i].i=i;
for (int i=;i<=n;i++) from[i][]=from[i][]=from[i][]=;
sort(a,a+n+,cmp2);
for (int i=;i<=n;i++)
while (i<n&&a[i+].y-a[i+].x==a[i].y-a[i].x) from[a[i+].i][]=a[i].i,i++;
sort(a,a+n+,cmp3);
for (int i=;i<=n;i++)
while (i<n&&a[i+].x+a[i+].y==a[i].x+a[i].y) from[a[i+].i][]=a[i].i,i++;
sort(a,a+n+,cmp4);
for (int i=;i<=n;i++)
while (i<n&&a[i+].x==a[i].x) from[a[i+].i][]=a[i].i,i++;
sort(a,a+n+,cmp);
memset(f,,sizeof(f));
f[]=;
for (int i=;i<=n;i++)
{
int t=i;ans[i]=f[i]=max(max(f[from[i][]],f[from[i][]]),f[from[i][]])+;
while (t<n&&a[t+].y==a[i].y)
t++,ans[t]=f[t]=max(max(f[from[t][]],f[from[t][]]),f[from[t][]])+;
int mx=-N;
for (int j=i;j<=t;j++)
g[j]=max(f[j],mx+j-i),mx=max(mx,f[j]);
mx=-N;
for (int j=t;j>=i;j--)
h[j]=max(f[j],mx+t-j),mx=max(mx,f[j]);
for (int j=i;j<=t;j++)
f[j]=max(g[j],h[j]);
i=t;
}
int x=,y=;
for (int i=;i<=n;i++) if (f[i]>f[x]) tot=f[i],y=x=i;
for (int i=;i<=n;i++) if (f[i]==tot) tagend[i]=;
cout<<tot<<endl;
memset(p,,sizeof(p));
for (int i=n;i>=;i--)
{
int t=i;
while (t>&&a[t-].y==a[i].y) t--;
if (t<=x&&x<=i)
{
if (f[x]==ans[x]) pre[x]=x;
for (int j=t;j<x;j++)
if (ans[j]+x-t==f[x]) pre[x]=j;
for (int j=i;j>x;j--)
if (ans[j]+i-x==f[x]) pre[x]=j;
x=pre[x];
if (f[from[x][]]+==ans[x]) pre[x]=from[x][];
if (f[from[x][]]+==ans[x]) pre[x]=from[x][];
if (f[from[x][]]+==ans[x]) pre[x]=from[x][];
x=pre[x];
}
for (int j=t;j<=i;j++)
if (tagend[j]&&f[j]==ans[j]) tagstart[j]=;
for (int j=t;j<=i;j++)
{
if (ans[j]>=&&flag[ans[j]]) tagstart[j]=;
if (tagend[j]) flag[f[j]+j-i]=;
}
for (int j=t;j<=i;j++)
if (tagend[j]) flag[f[j]+j-i]=;
for (int j=i;j>=t;j--)
{
if (ans[j]>=&&flag[ans[j]]) tagstart[j]=;
if (tagend[j]) flag[f[j]+t-j]=;
}
for (int j=i;j>=t;j--)
if (tagend[j]) flag[f[j]+t-j]=;
for (int j=t;j<=i;j++)
if (tagstart[j])
{
if (f[from[j][]]+==ans[j]) tagend[from[j][]]=,addedge(from[j][],j,N-),degree[from[j][]]++,degree[j]--;
if (f[from[j][]]+==ans[j]) tagend[from[j][]]=,addedge(from[j][],j,N-),degree[from[j][]]++,degree[j]--;
if (f[from[j][]]+==ans[j]) tagend[from[j][]]=,addedge(from[j][],j,N-),degree[from[j][]]++,degree[j]--;
}
i=t;
}
print(y);
cout<<endl;
for (int i=;i<=n;i++)
if (degree[i]>) addedge(i,T,degree[i]);
else addedge(S,i,-degree[i]);
for (int i=;i<=n;i++) addedge(SS,i,N),addedge(i,ST,N);
addedge(ST,SS,N);
dinic(S,T);
tot=;
dinic(ST,SS);
cout<<N-tot;
return ;
}