CF1517H Fly Around the World

在听了张博士的故事后，Wowo 决定计划一次自己的环球飞行。 他已经在世界地图上选定了 $n$ 个检查点。由于地形和云层的影响，他不能飞得太高或太低。具体来说，设 $b_i$ 表示 Wowo 的飞机在第 $i$ 个检查点的高度，需要满足 $x_i^- \leq b_i \leq x_i^+$，其中 $x_i^-$ 和 $x_i^+$ 是给定的整数，$i$ 的取值范围为 $1$ 到 $n$。 Wowo 的飞机的爬升/下降角度也有限制。例如，飞机不能进行 $90$ 度的爬升。具体来说，需要满足 $y_i^- \leq b_i - b_{i-1} \leq y_i^+$，其中 $y_i^-$ 和 $y_i^+$ 是给定的整数，$i$ 的取值范围为 $2$ 到 $n$。 最后一个限制是爬升或下降的速度。出于安全考虑，飞机应当缓慢改变角度。具体来说，需要满足 $z_i^- \leq (b_i - b_{i-1}) - (b_{i-1} - b_{i-2}) \leq z_i^+$，其中 $z_i^-$ 和 $z_i^+$ 是给定的整数，$i$ 的取值范围为 $3$ 到 $n$。 考虑到所有这些限制，Wowo 发现要选择各检查点的高度太难了。请你帮 Wowo 判断是否存在一个实数序列 $b_1, \ldots, b_n$ 满足上述所有约束条件。

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 66\,666$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 100\,000$）。 接下来的 $n$ 行，每行包含两个整数 $x_i^-$、$x_i^+$（$-10^8 \leq x_i^- \leq x_i^+ \leq 10^8$），表示 $b_i$ 的下界和上界。 接下来的 $n-1$ 行，每行包含两个整数 $y_{i+1}^-$、$y_{i+1}^+$（$-10^8 \leq y_{i+1}^- \leq y_{i+1}^+ \leq 10^8$），表示 $b_{i+1} - b_i$ 的下界和上界。 接下来的 $n-2$ 行，每行包含两个整数 $z_{i+2}^-$、$z_{i+2}^+$（$-10^8 \leq z_{i+2}^- \leq z_{i+2}^+ \leq 10^8$），表示 $(b_{i+2} - b_{i+1}) - (b_{i+1} - b_i)$ 的下界和上界。 保证所有测试用例中 $n$ 的总和不超过 $200\,000$。 保证如果将每个约束放宽 $10^{-6}$（即将 $x_i^-, y_i^-, z_i^-$ 减小 $10^{-6}$，将 $x_i^+, y_i^+, z_i^+$ 增加 $10^{-6}$），答案不会发生变化。

对于每个测试用例，如果存在满足所有约束条件的序列 $b_1, \ldots, b_n$，输出 YES，否则输出 NO。无需输出具体的序列。

在第一个测试用例中，所有 $b_i$ 都在 $[0,1]$ 区间内。由于有约束 $1 = y_2^- \leq b_2 - b_1 \leq y_2^+ = 1$，所以 $b_2 - b_1$ 必须为 $1$，即 $b_2 = 1$ 且 $b_1 = 0$。接着由 $1 = y_3^- \leq b_3 - b_2 \leq y_3^+ = 1$，可得 $b_3 = 2$。这与 $b_3 \leq 1$ 的约束矛盾，因此无解。 在第二个测试用例中，可以让所有 $b_i$ 都为 $0$。 在第三个测试用例中，一组可行解为 $b_1 = 0$，$b_2 = 1/3$，$b_3 = 2/3$，$b_4 = 1$。 由 ChatGPT 4.1 翻译