#P4081. [Wf2014]Skiing

[Wf2014]Skiing

[ICPC2014 WF] Skiing

题目描述

滑雪运动员从 (0,0)(0,0) 出发,赛道的下坡方向是 yy 轴正方向。其速度在 yy 方向的分量始终为 vyv_y,在 xx 方向的初始速度为 00。运动员可以改变横向加速度,但装备限制了其大小,因此每一时刻都有 ∣ax∣≤amax⁡|a_x|\le a_{\max}。

赛道上有若干目标。请找出滑雪运动员在一次滑行中按经过顺序所能取得的最长目标编号序列。

样例 1 中经过三个目标的滑行路线

图中为样例 1 的一条最优路线,运动员经过四个目标中的三个。若减小 amax⁡a_{\max},能够经过的目标可能变少。

输入格式

输入只有一组数据。第一行包含三个整数 n,vy,amax⁡n,v_y,a_{\max}(0≤n≤2500\le n\le250,0≤vy≤1050\le v_y\le10^5,0≤amax⁡≤1070\le a_{\max}\le10^7),分别表示目标数、纵向速度和横向加速度的上限。纵向速度以米每小时计,横向加速度以米每二次方小时计。

接下来 nn 行,第 ii 行包含两个整数 xi,yix_i,y_i(−105≤xi,yi≤105-10^5\le x_i,y_i\le10^5),表示目标 ii 的坐标,单位是米。目标从 11 到 nn 编号。

输出格式

按经过顺序输出最长的目标编号序列。若有多个最长序列,只输出按编号比较的字典序最小者。例如,序列 2 15 小于序列 10 15。若无法经过任何目标,输出 Cannot visit any targets。

保证将 amax⁡a_{\max} 扰动不超过 0.10.1 时,答案不变。

样例 #1

样例输入 #1

4 100 400
-100 100
50 200
-100 300
150 300

样例输出 #1

1 2 4

样例 #2

样例输入 #2

1 100 100
1000 10

样例输出 #2

Cannot visit any targets