A1-2017级算法上机第一次练习赛 O AlvinZH的儿时梦想——运动员篇

时间:2021-02-09 09:51:19

题目描述

AlvinZH儿时有很多梦想,这一次他想成为一名运动员。他开始每天跑步,刻苦训练。他报名参加了一个"奇怪"的跑步比赛,下面是比赛的"奇怪"规则:

参赛选手将在环形跑道的随机位置出发。为了加快比赛进程,在比赛过程中,如果两个人相遇,裁判将立即测定双方耐力值,耐力值低的选手会被淘汰。当比赛人数为1时比赛结束。

这是一个比赛吗?本题当然不是想问你这个,想问的是比赛进行的时间。

难题慎入

输入

第一个数为数据组数TT≤100)。

每组数据第一行为参赛人数n环形跑道长度L2≤n≤10^42≤L≤10^5)。

接下来的n行,每行三个整数posvpower,代表参赛选手的初始位置、速度、耐力值(0≤posL0≤|vi|≤10^50power≤10^5,且选手之间posvpower互不相同)。

输出

对于每组数据,输出一行,为距离比赛结束需要的时间。

输入样例

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

相遇时间是关键!

思路