小球下落

小球下落

这是一个基于如下图装置的一个游戏。

装置包括一组水平放置的，高度不同的，长度不同的平板。地板被视为高度最低的平板。

在0时刻，从一个给定的位置，一个小球自由落下。小球以一个固定的每秒1米的速度下落。当小球到达某一平板后，它可以根据游戏者的选择，以同样的速度（每秒1米）滚向左端或右端。当它到达平板的边缘时，它继续垂直下落。小球不允许一次（在两块平板之间）下落超过max米。

任务

编写一个程序找出一个小球在平板上滚动的方法，使得不中断的尽快的到达地面。

输入

file name: fall.in

第一行: n x y max

· 四个整型数 平板的数目，小球起始位置的x,y坐标，最大允许下落的距离

第2..n+1行:

· 三个整型数－第i个平板被放置在 高度,水平位于 与 （包括与 ）,( < , i=1..n).

注意:

· 小球的直径和平板的厚度忽略不计。如果小球恰好落到平板的边缘则被认为一次下落到该平板。

· 任意两块平板不存在公共点

· 测试数据总存在解

· 所有给定的尺寸均为米

输出

file name: fall.out

第一行:时间

· 一个整数，小球到达地面的时间

接下来每行为：

p t d

· 三个整数，表示在t时刻，小球撞及平板p，并且向方向d滚动 (0表示左，1表示右)。

· 不包含撞及地面的情况

· 必须按小球撞及平板的时间递增顺序输出

注意

· 可能有多解，只要求出一种解。

限制

· 1 n 1000

· -xx0 , xx0 (i=1..n)

· 0 < < y xx0

example

fall.in 　　　fall.out

3 8 17 20 23

0 10 8 　　 　　 2 4 1

0 10 13 1 11 1

4 14 3 　　　　　3 16 1