#P6901. [ICPC 2014 WF] skiing
[ICPC 2014 WF] skiing
Description
滑雪运动员进行的一次训练可以看作平面上一条从 出发的曲线,这条曲线在 轴正方向上的速度是 ,由于装备限制,在 轴上的加速度不得超过 。滑雪运动员在 轴上的速度从 开始。
在这一次训练中,滑雪运动员需要经过所有 个目标点 中尽可能多的目标点,现在他希望你通过控制他每一时刻的加速度,实现这个目标。
Input Format
第一行三个整数 分别表示目标点数, 轴速度(米每秒)以及 轴加速度上限(米每二次方秒)。
接下来 行每行两个整数 表示目标点的横坐标(米)以及纵坐标(米)。
Output Format
按照目标点被经过的顺序输出最长的目标点序列。若有多个可能的答案,输出字典序最小的。若运动员不能经过任意一个目标点,输出 Cannot visit any targets。
为了避免浮点误差,你可以假设对 进行不超过 的扰动的情况下,答案不变。
4 100 400
-100 100
50 200
-100 300
150 300
1 2 4
1 100 100
1000 10
Cannot visit any targets
Hint
$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 开始。
一句话の题意:输入一些数,输出一些数(或字符串),使输出符合要求。
京公网安备 11011102002149号