#P18480. Egg Drop Challenge

Egg Drop Challenge

Egg Drop Challenge

一年一度的扔鸡蛋挑战即将开始!共有 nn 名参与者,他们站在同一栋建筑的不同楼层。第 ii 名参与者站在第 ii 层,离地面的高度为 hih_i。第 nn 层的参与者最初拿着一枚鸡蛋。大家希望在保证安全的前提下,尽快把鸡蛋送到第一层。

当第 ii 名参与者拿着鸡蛋时,可以用任意一个介于 00 和 viv_i 之间(含端点)的实数速度,竖直向下扔出鸡蛋。

当鸡蛋经过第 ii 名参与者,即到达高度 hih_i 时,如果此时速度不超过 uiu_i,这名参与者可以选择接住鸡蛋,也可以让它继续下落。接住鸡蛋意味着让它完全停止。只有当第一名参与者接住鸡蛋时,才算把鸡蛋安全送到第一层。

鸡蛋在下落过程中受到重力加速度 gg。为简化计算,假设没有空气阻力,且 g=1g=1。接住和扔出鸡蛋都在瞬间完成,不消耗时间。鸡蛋可以跳过任意中间楼层,无须让每个人都接住。

请计算安全把鸡蛋送到第一层所需的最短时间。如果无法做到,请报告无解。

输入格式

第一行一个整数 nn,表示参与者人数,2≤n≤3⋅1052\le n\le 3\cdot10^5。

接下来 nn 行,第 ii 行包含三个整数 hi,vi,uih_i,v_i,u_i,分别表示第 ii 名参与者的高度、最大扔出速度和最大可接受的接住速度:

  • 1≤hi≤10181\le h_i\le10^{18};
  • 1≤vi,ui≤1091\le v_i,u_i\le10^9;
  • 对所有 1≤i<n1\le i<n,保证 hi<hi+1h_i<h_{i+1}。

输入只有一个实例,没有测试实例数 TT。

输出格式

如果存在满足所有条件的方案,输出一个实数,表示所需最短时间。绝对误差或相对误差不超过 10−610^{-6} 的答案均被接受。

如果不存在方案,输出 −1-1。

样例 1

5
2 1 7
14 6 4
18 1 7
21 2 5
28 4 10
6.00000000000000000000

样例 2

2
1 1 4
10 5 1
-1

说明

如果鸡蛋以速度 vv 开始下落,那么经过 tt 秒后,其速度为 v+gtv+gt;本题中为 v+tv+t。它下落的距离为 vt+gt2/2vt+gt^2/2;本题中为 vt+t2/2vt+t^2/2。

样例 1 的一个最优方案如下。

  1. 第 5 名参与者以速度 44 扔出鸡蛋。经过 22 秒,它下落 4⋅2+22/2=104\cdot2+2^2/2=10 米,速度为 66,第 3 名参与者可以接住它。
  2. 第 3 名参与者以速度 11 扔出鸡蛋,经过 22 秒,第 2 名参与者接住它。
  3. 第 2 名参与者以速度 55 扔出鸡蛋,再经过 22 秒,第 1 名参与者接住它。

总时间为 66 秒。

样例 2 中,即使第 2 名参与者以速度 00 扔出鸡蛋,到达第一层时速度仍大于 44,因此无法安全送达。