QOJ.ac

QOJ

時間限制: 2 s 記憶體限制: 2048 MB 總分: 100

#7674. 滑雪

统计

众所周知,ACM ICPC 并不是今年在俄罗斯举办的唯一重大体育赛事。几个月前,2014 年冬季奥运会在索契举行,距离叶卡捷琳堡约 3000 公里。

在越来越多的运动项目中,决定比赛胜负的不仅是运动员的能力,还有他们的装备。例如在滑雪速降中,拥有最新的滑雪技术装备能让运动员提高速度并改善转弯能力。

你受聘来确定最新的滑雪技术对滑雪者在速降赛道上导航能力的影响。赛道包含多个目标位置,滑雪者希望尽可能多地经过这些目标。自然地,滑雪技术越好,完成这一目标就越容易。

为简化起见,使用一个二维坐标系,滑雪者从位置 $(0,0)$ 出发,“下坡”方向对应 $y$ 轴正方向。

假设运动员速度的 $y$ 分量为常数 $v_y$。运动员可以改变横向($x$ 方向)的速度,但滑雪装备将其限制在最大横向加速度 $a_{max}$。滑雪者出发时的横向速度为 0。

图 J.1:经过三个目标的速降滑雪路径

在图 J.1 中(对应第一个样例输入),最优路径经过了四个可能目标中的三个。如果 $a_{max}$ 更小,那么滑雪者可能只能经过两个或更少的目标。

输入格式

输入包含单个测试用例。第一行包含三个整数 $n$、$v_y$ 和 $a_{max}$($0 \le n \le 250$,$0 \le v_y \le 10^5$ 且 $0 \le a_{max} \le 10^7$),其中 $n$ 是目标数量,$v_y$ 是滑雪者速度的 $y$ 分量,$a_{max}$ 是最大横向加速度。这里 $v_y$ 的单位为米/小时,$a_{max}$ 的单位为米/小时$^2$。

接下来有 $n$ 行,每行包含两个整数 $x_i$ 和 $y_i$($-10^5 \le x_i, y_i \le 10^5$)。这些给出了赛道上每个待访问目标的坐标。所有坐标单位均为米。目标按给出的顺序编号为 $1, 2, \dots, n$。

输出格式

显示运动员在单次滑行中能够经过的目标的最长序列。按访问顺序显示目标编号。如果存在多个长度相同的最优序列,仅显示字典序最小的一个。(例如,序列 2 15 会排在序列 10 15 之前。)如果运动员无法经过任何目标,则打印 Cannot visit any targets

为了确保浮点数稳定性,你可以假设如果 $a_{max}$ 的扰动在 0.1 以内,答案不会改变。

样例

样例输入 1

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

样例输出 1

1 2 4

样例输入 2

1 100 100
1000 10

样例输出 2

Cannot visit any targets

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.