$n$ 个人站在一个数轴上，它们的坐标均为正整数，且小于 $10^6$。对于每个人，都有一个面对的方向 (左和右) 以及它的速度。
你可以在一个坐标为非负整数，且不超过 $10^6$ 的位置上放置一个炸弹 (???)，并引爆它 (??????)，这时，所有的人都会按照他们面对的方向以他们的速度跑起来。与此同时，两条奇怪的射线会以 $s$ 的速度从炸弹的位置发射出来——一条向右、一条向左。当然，速度 $s$ 严格大于人的跑步速度。
这些射线之所以奇怪，是因为如果某一个时刻，射线的位置与某个人的位置重合，且该射线的方向与那个人跑步的方向一致，则他跑步的速度会立即增加射线的速度 $s$。
你需要在一个地方放置一个炸弹，使得目标时间——即有一个人到达过位置 $0$，且还有一个人到达过位置 $10^6$ 的时间——尽可能地小。换句话说，找到最小的时间 $t$，使得存在那么一个放炸弹的位置，使得前 $t$ 个单位时间内有人到达过位置 $0$，且有人到达过位置 $10^6$ (不必同时)。
第一行包含两个正整数 $n, s$ ($2 \leq n \leq 10^5, 2 \leq s \leq 10^6$)，表示人的个数和射线的速度。
接下来的 $n$ 行描述人。其中第 $i$ 行包含三个正整数 $x_i, v_i, t_i$ ($0 < x_i < 10^6, v_i < s, t_i \in \{1, 2\}$)，分别表示第 $i$ 个人的坐标、他跑步的速度以及他跑步的方向，其中 $1$ 为左 (负方向)，$2$ 为右 (正方向)。
输出目标时间的最小值。你的答案被判定为正确当且仅当绝对误差或相对误差不超过 $10^{-6}$。
目标时间最小值这玩意儿嘛，可以考虑二分。二分目标时间后就是判定是否存在这么一个放炸弹的位置的问题 (题面好奇怪)。
先注意这个奇怪的题面，它的要求是至少有一个人到达位置 $0$ 且至少有一个人到达位置 $10^6$，没有说所有人都要到达二者这一哦~ 因此，我们只需检验左边是否有人到达和右边是否有人到达即可。
考虑枚举每个人，不妨设他是向左走的，则它的坐标就是要走的距离，不妨记作 $x_0$，速度记为 $v_0$，射线的速度记作 $v$ ($v > v_0$)，二分的那个时间记作 $t$。
由于它的速度只会增加不会减少，也就是说时间只会减少不会增加，因此如果它按原来的速度就可以跑到终点，即 $x_0 \leq v_0 t$，则这个人就一定能跑到左边。(那么左边就不用考虑了哈哈哈)
接下来考虑 $x_0 > v_0 t$，即按照原来的速度跑不到终点的情况。因此考虑使用炸弹！不妨设炸弹的位置为 $x$，显然由题意 $x_0 \leq x \leq 10^6$ (如果 $x < x_0$ 则射线方向与跑步方向不同)，接下来就是解出总时间。
由小学奥数追及问题得，射线追到人的时间应该是 $t_1 = \dfrac {x - x_0} {v - v_0}$，此时追到的位置应该是 $x_1 = x - v t_1 = x - v \dfrac {x - x_0} {v - v_0} = \dfrac {x_0 v - v_0 x} {v - v_0}$，这时需要保证追到的位置 $\geq 0$，即 $x_0 v - v_0 x \geq 0$，得到第一个不等式 $x \leq \dfrac {x_0} {v_0} \cdot v$。
接下来人的速度就应该是 $v_1 = v + v_0$，要走的距离就是 $x_1 = \dfrac {x_0 v - v_0 x} {v - v_0}$，故时间 $t_2 = \dfrac {x_1} {v_1} = \dfrac {x_0 v - v_0 x} {v^2 - v_0^2}$，总时间为 $t_总 = t_1 + t_2 = \dfrac {x v - x_0 v_0} {v^2 - v_0^2}$，它需要满足 $t_总 \leq t$，因此我们能解得 $x \leq \dfrac {x_0 v_0 + (v^2 - v_0^2) t} v$，故 $x$ 需要满足 $x_0 \leq x \leq \min \left\{ 10^6, \dfrac {x_0 v} {v_0}, \dfrac {x_0 v_0 + (v^2 - v_0^2) t} v \right\}$。
那么，对于每个 (向左走的) 人，我们都可以找到一个范围，使得 $l_i \leq x \leq r_i$ (注意！可能是空集，此时需要特判掉)，我们最后取这些集合的并 (因为至少一个人能到达就 OK)。
对向右走的人，完全类似地也可以得到一堆范围，还是求个并。最后，如果两边有交集，就说明该 $t$ 值有解，否则无解。注意判断的时候直接使用下界的 $\max$ 是否小于等于上界的 $\min$ 即可。总时间复杂度 $O \left( n |\log eps| \right)$。
#include <bits/stdc++.h>
#define N 100034
#define Y 1000000
using namespace std;
const double eps = 3e-9;
int n, i, j;
int x[N], v[N];
double L, R, M;
inline void up(double &x, const double y) {x < y ? x = y : 0.0;}
inline void down(double &x, const double y) {x > y ? x = y : 0.0;}
inline bool test(double t){
bool rev = false;
double v0, x0, l, r;
double li = Y, ls = 0.0, ri = Y, rs = 0.0;
for(i = 1; i <= n; ++i){
v0 = (double)((rev = v[i] > 0) ? v[i] : -v[i]);
x0 = (double)(rev ? Y - x[i] : x[i]);
if(x0 <= v0 * t) {l = 0.0; r = Y;}
else{
l = x0; down(r = Y, x0 / v0 * (double)*v);
down(r, (x0 * v0 + ((double)*v * *v - v0 * v0) * t) / (double)*v);
// x <= [x_0 v_0 + (v^2 - v_0^2) t] / v
}
if(l > r + eps) continue;
rev ? down(ri, Y - r) : down(li, l);
rev ? up(rs, Y - l) : up(ls, r);
}
return ceil(max(li, ri)) <= floor(min(ls, rs)) + eps;
}
int main(){
scanf("%d%d", &n, v);
for(i = 1; i <= n; ++i){
scanf("%d%d%d", x + i, v + i, &j);
j == 1 ? v[i] = -v[i] : 0;
}
for(L = 0.0, R = Y; R - L > eps; )
test(M = (L + R) * 0.5) ? R = M : (L = M);
printf("%.9lg\n", (L + R) * 0.5);
return 0;
}
坑1：已经说过，注意题面中要求是至少一个人，而不是所有人都要到达。
坑2：炸弹的坐标是整数，因此最后判断的时候需要取上/下整，即 $\left \lceil \max\{ \inf L, \inf R \} \right \rceil \leq \left \lfloor \min\{ \sup L, \sup R \} \right \rfloor$。
坑3：注意对于某些人，求得的合法的炸弹放置区间可能是空集 (即 $l_i > r_i$)，此时应直接 continue;，不能继续取 $\min$ (或 $\max$)。