#P2340. 山形压缩

    ID: 1371 传统题 3000ms 256MiB 尝试: 6 已通过: 1 难度: 6 上传者: 标签>CF2000提高DAG 动态规划增量维护有理数精确运算路径恢复

山形压缩

题目描述

YY 面前有一座用折线表示的山。山的轮廓依次经过 NN 个点 (X1,Y1),(X2,Y2),…,(XN,YN)(X_1,Y_1),(X_2,Y_2),\ldots,(X_N,Y_N),并依次用线段连接相邻的点。

YY 希望删除一部分中间点,然后按原顺序用线段连接剩余点,从而用更少的点近似原来的山形。第 11 个点和第 NN 个点不能删除。

若新旧两条折线在每一个横坐标处的高度差的绝对值均不超过 Δ\Delta,则称它们是近似的。

请找出一种删除方案,使新折线与原折线近似,并且删除的点数最多。

输入格式

第一行包含两个非负整数 NN 和 Δ\Delta,其中 3≤N≤100003\le N\le 10000。

接下来 NN 行,每行包含两个非负整数 Xi,YiX_i,Y_i,表示第 ii 个点的坐标。

数据保证:

  • 0≤Xi,Yi≤200000\le X_i,Y_i\le 20000;
  • X1<X2<⋯<XNX_1<X_2<\cdots<X_N;
  • Δ≥0\Delta\ge 0。

输出格式

第一行输出一个非负整数 MM,表示删除的点数,且 MM 应尽可能大。

接下来输出 MM 行,每行一个被删除点的编号(从 11 开始编号),编号必须严格递增。

如果存在多种最优删除方案,输出其中任意一种即可。当没有点可以删除时,输出一行 0。

输入样例

5 1
0 0
2 4
4 7
8 3
10 0

输出样例

2
2
4

样例说明

删除第 22、44 个点后,保留 (0,0)(0,0)、(4,7)(4,7) 和 (10,0)(10,0)。新的折线与原折线的最大高度差不超过 11,且删点数已达到最大值。