#P2340. 山形压缩
山形压缩
题目描述
YY 面前有一座用折线表示的山。山的轮廓依次经过 个点 ,并依次用线段连接相邻的点。
YY 希望删除一部分中间点,然后按原顺序用线段连接剩余点,从而用更少的点近似原来的山形。第 个点和第 个点不能删除。
若新旧两条折线在每一个横坐标处的高度差的绝对值均不超过 ,则称它们是近似的。
请找出一种删除方案,使新折线与原折线近似,并且删除的点数最多。
输入格式
第一行包含两个非负整数 和 ,其中 。
接下来 行,每行包含两个非负整数 ,表示第 个点的坐标。
数据保证:
- ;
- ;
- 。
输出格式
第一行输出一个非负整数 ,表示删除的点数,且 应尽可能大。
接下来输出 行,每行一个被删除点的编号(从 开始编号),编号必须严格递增。
如果存在多种最优删除方案,输出其中任意一种即可。当没有点可以删除时,输出一行 0。
输入样例
5 1
0 0
2 4
4 7
8 3
10 0
输出样例
2
2
4
样例说明
删除第 、 个点后,保留 、 和 。新的折线与原折线的最大高度差不超过 ,且删点数已达到最大值。