题目描述
AlvinZH儿时有很多梦想,这一次他想成为一名运动员。他开始每天跑步,刻苦训练。他报名参加了一个"奇怪"的跑步比赛,下面是比赛的"奇怪"规则:
参赛选手将在环形跑道的随机位置出发。为了加快比赛进程,在比赛过程中,如果两个人相遇,裁判将立即测定双方耐力值,耐力值低的选手会被淘汰。当比赛人数为1时比赛结束。
这是一个比赛吗?本题当然不是想问你这个,想问的是比赛进行的时间。
难题慎入
输入
第一个数为数据组数T(T≤100)。
每组数据第一行为参赛人数n和环形跑道长度L(2≤n≤10^4,2≤L≤10^5)。
接下来的n行,每行三个整数pos、v、power,代表参赛选手的初始位置、速度、耐力值(0≤pos<L,0≤|vi|≤10^5,0<power≤10^5,且选手之间pos、v、power互不相同)。
输出
对于每组数据,输出一行,为距离比赛结束需要的时间。
输入样例
2
2 4
0 3 1
2 2 2
10 100
0 2 10
10 -3 15
20 5 5
30 -4 8
40 13 7
50 20 3
60 2 50
70 -30 2
80 11 14
90 12 16
输出样例
2.000
8.889
HINT
相遇时间是关键!
思路