P6901 [ICPC 2014 WF] skiing

题目描述

滑雪运动员进行的一次训练可以看作平面上一条从 $(0, 0)$ 出发的曲线,这条曲线在 $y$ 轴正方向上的**速度**是 $v_y$,由于装备限制,在 $x$ 轴上的**加速度**不得超过 $a_{max}$。滑雪运动员在 $x$ 轴上的速度从 $0$ 开始。 在这一次训练中,滑雪运动员需要经过所有 $n$ 个目标点 $(x_i, y_i)$ 中尽可能多的目标点,现在他希望你通过控制他每一时刻的加速度,实现这个目标。

输入格式

第一行三个整数 $n, v_y, a_{max}$ 分别表示目标点数,$y$ 轴速度(米每秒)以及 $x$ 轴加速度上限(米每二次方秒)。 接下来 $n$ 行每行两个整数 $x, y$ 表示目标点的横坐标(米)以及纵坐标(米)。

输出格式

按照目标点被经过的顺序输出最长的目标点序列。若有多个可能的答案,输出字典序最小的。若运动员不能经过任意一个目标点,输出 `Cannot visit any targets`。 为了避免浮点误差,你可以假设对 $a_{max}$ 进行不超过 $0.1$ 的扰动的情况下,答案不变。

说明/提示

$0\le n\le 250, 0\le v_y\le 10^5 , 0\le a_{max}\le 10^7 , −10^5\le x, y\le 10^5$ , 目标点编号从 1 开始。 ~~一句话の题意:输入一些数,输出一些数(或字符串),使输出符合要求。~~