Preparando MOJI
After hearing the story of Dr. Zhang, Wowo decides to plan his own flight around the world.
He already chose $$$n$$$ checkpoints in the world map. Due to the landform and the clouds, he cannot fly too high or too low. Formally, let $$$b_i$$$ be the height of Wowo's aircraft at checkpoint $$$i$$$, $$$x_i^-\le b_i\le x_i^+$$$ should be satisfied for all integers $$$i$$$ between $$$1$$$ and $$$n$$$, where $$$x_i^-$$$ and $$$x_i^+$$$ are given integers.
The angle of Wowo's aircraft is also limited. For example, it cannot make a $$$90$$$-degree climb. Formally, $$$y_i^-\le b_i-b_{i-1}\le y_i^+$$$ should be satisfied for all integers $$$i$$$ between $$$2$$$ and $$$n$$$, where $$$y_i^-$$$ and $$$y_i^+$$$ are given integers.
The final limitation is the speed of angling up or angling down. An aircraft should change its angle slowly for safety concerns. Formally, $$$z_i^- \le (b_i - b_{i-1}) - (b_{i-1} - b_{i-2}) \le z_i^+$$$ should be satisfied for all integers $$$i$$$ between $$$3$$$ and $$$n$$$, where $$$z_i^-$$$ and $$$z_i^+$$$ are given integers.
Taking all these into consideration, Wowo finds that the heights at checkpoints are too hard for him to choose. Please help Wowo decide whether there exists a sequence of real numbers $$$b_1, \ldots, b_n$$$ satisfying all the contraints above.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 66\,666$$$). Description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 100\,000$$$).
The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i^-$$$, $$$x_i^+$$$ ($$$-10^8\le x_i^-\le x_i^+\le 10^8$$$) denoting the lower and upper bound of $$$b_i$$$.
The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$y_{i+1}^-$$$, $$$y_{i+1}^+$$$ ($$$-10^8\le y_{i+1}^-\le y_{i+1}^+\le 10^8$$$) denoting the lower and upper bound of $$$b_{i+1}-b_i$$$.
The $$$i$$$-th of the next $$$n-2$$$ lines contains two integers $$$z_{i+2}^-$$$, $$$z_{i+2}^+$$$ ($$$-10^8\le z_{i+2}^-\le z_{i+2}^+\le 10^8$$$) denoting the lower and upper bound of $$$(b_{i+2}-b_{i+1}) - (b_{i+1}-b_i)$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$200\,000$$$.
It is guaranteed that relaxing every constraint by $$$10^{-6}$$$ (i.e., decrease $$$x_i^-, y_i^-, z_i^-$$$ by $$$10^{-6}$$$ and increase $$$x_i^+, y_i^+, z_i^+$$$ by $$$10^{-6}$$$) will not change the answer.
For each test case, output YES if a sequence $$$b_1,\ldots, b_n$$$ satisfying the constraints exists and NO otherwise. The sequence $$$b_1,\ldots, b_n$$$ is not required.
4 3 0 1 0 1 0 1 1 1 1 1 -100 100 3 -967 541 -500 834 -724 669 -858 978 -964 962 -645 705 4 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 4 0 0 33 34 65 66 100 100 0 100 0 100 0 100 0 0 0 0
NO YES YES NO
In the first test case, all $$$b_i$$$'s are in $$$[0,1]$$$. Because of the constraints $$$1=y_2^-\le b_2-b_1\le y_2^+=1$$$, $$$b_2-b_1$$$ must be $$$1$$$. So $$$b_2=1$$$ and $$$b_1=0$$$ must hold. Then by $$$1=y_3^-\le b_3-b_2\le y_3^+=1$$$, $$$b_3$$$ equals $$$2$$$. This contradicts the constraint of $$$b_3\le 1$$$. So no solution exists.
In the second test case, we can let all $$$b_i$$$'s be $$$0$$$.
In the third test case, one possible solution is $$$b_1=0$$$, $$$b_2=1/3$$$, $$$b_3=2/3$$$, $$$b_4=1$$$.
Informação
Provedor Codeforces
Código CF1517H
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:13:47
Relacionados