#5079. 钟离移山

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Star

题目描述

题目背景

在一个风和日丽的下午,Star从群玉阁跳了下来,落在了一座山的山顶上,发现他的正前方有很多山。

于是,他很好奇请钟离移走一些山后,他最多能看到多少座山。

题目描述

Star前方有 n 座山,他知道每座山相对自己所在的这座的高度 h_i 和距离 d_i 。钟离可以移走任何一座山,也可以不移。

求他能看到的最多的山的个数 m ,和看到的是哪几个山 (输出一种方案)。

输入格式

1 行一个整数 n ,表示山的个数。

接下来 n 行每行两个整数 h_i , d_i ,表示相对高度和距离,数据保证 d_i 递增。

输出格式

第一行一个整数 m 表示最多能看到的山的个数。

第二行输出一种可行的方案,按照从近到远的顺序输出山的编号,每个数之间用空格隔开。若存在多组解,输出字典序最小的一组。

样例

样例输入 #1

7
1 1
4 2
3 3
8 4
20 5
18 6
35 7

样例输出 #1

4
1 2 5 7

样例输入 #2

10
-23 2
33 3
11 4
-107 7
30 8
46 9
-94 12
239 13
39 14
-330 19

样例输出 #2

5
1 3 5 6 8 

数据范围与提示

样例说明

如图

zhongli.png

可行的方案有 [1, 2, 5, 7] [1, 4, 5, 7] [3, 4, 5, 7] 三种,其中 [1, 2, 5, 7] 最小。

注意:如果山顶在同一条线上视为后面的那座看不到

数据范围
  • 对于 50\% 的数据,满足 0<n\le10000 .

  • 对于另外 50\% 的数据,满足 10000<n\le200000 .

对于 100\% 的数据,满足 0<n\le200000 0<d_i<10^9 -10^9 \le h_i \le 10^9 .