[SGU526] Running Hero / 奔跑的英雄

题目描述

阿拉丁正在一条很长的洞穴中奔跑。把洞穴抽象成一条 $x$ 轴，阿拉丁是轴上的一个点。他可以瞬间改变速度，且任意时刻速度的绝对值不能超过 $v$。

阿拉丁从位置 $0$、时刻 $0$ 出发。茉莉公主位于位置 $G$。

洞穴中会有 $n$ 块石头落下。第 $i$ 块石头在时刻 $t_i$ 落地，并覆盖开区间 $(x_{1,i},x_{2,i})$。如果在石头落地的那个瞬间，阿拉丁的位置严格位于这个开区间内部，他就会死亡；位于端点 $x_{1,i}$ 或 $x_{2,i}$ 是安全的。

茉莉所在的位置有防护，因此如果阿拉丁已经在某块石头落下的时刻或更早到达 $G$，之后的落石都不再影响结果。

请判断阿拉丁能否安全到达茉莉。如果可以，请给出一组使到达时间最短的行动方案。

输入格式

第一行三个整数 $v,G,n$，分别表示最大速度、茉莉的位置和落石数量。

接下来 $n$ 行，每行三个整数 $x_{1,i},x_{2,i},t_i$，表示一块石头覆盖的区间端点以及落地时刻。

输出格式

如果无法到达，输出一行：

-1

否则，第一行输出整数 $k$，表示行动指令数量。

接下来 $k$ 行，每行两个实数 $w,t$，表示以恒定速度 $w$ 运动 $t$ 秒。要求：

• $|w|\le v$；
• $t>0$；
• $w<0$ 表示向负方向运动，$w>0$ 表示向正方向运动，$w=0$ 表示原地等待；
• 所有指令连续执行；
• 执行完毕后到达 $G$，且总用时必须最小；
• 指令数不得超过 $10000$。

实数请输出足够精度，建议至少保留 $9$ 位小数。

如果存在多种最优方案，可以输出任意一种。

数据范围

$1\le v\le10^5$，$0<|G|\le10^5$，$0\le n\le3000$。

$-10^5\le x_{1,i}\le x_{2,i}\le10^5$，$1\le t_i\le10^5$。

样例

样例输入

5 35 2
-5 6 1
5 35 9

样例输出

一种合法输出为：

2
-5.000000000000000 1.000000000000000
5.000000000000000 8.000000000000000