После того, как Уово услышал историю доктора Чжан, он решил спланировать свой собственный полет вокруг света.
Он уже выбрал $$$n$$$ контрольных точек на карте мира. Из-за формы рельефа и облаков, он не может лететь слишком высоко или слишком низко. Формально, пусть $$$b_i$$$ будет высота самолета Уово на контрольной точке $$$i$$$. Для всех целых $$$i$$$ между $$$1$$$ и $$$n$$$ должно выполняться $$$x_i^-\le b_i\le x_i^+$$$, где $$$x_i^-$$$ и $$$x_i^+$$$ — данные вам целые числа.
Угол полета самолета Уово тоже ограничен. Например, он не может лететь вертикально вверх под $$$90$$$ градусов. Формально, $$$y_i^-\le b_i-b_{i-1}\le y_i^+$$$ должно выполняться для всех целых $$$i$$$ между $$$2$$$ и $$$n$$$, где $$$y_i^-$$$ и $$$y_i^+$$$ — данные вам целые числа.
Последнее ограничение связано со скоростью изменения угла. Самолет должен делать это плавно из соображений безопасности. Формально, $$$z_i^- \le (b_i - b_{i-1}) - (b_{i-1} - b_{i-2}) \le z_i^+$$$ должно выполняться для всех целых $$$i$$$ между $$$3$$$ и $$$n$$$, где $$$z_i^-$$$ и $$$z_i^+$$$ — данные вам целые числа.
Принимая во внимание все эти ограничения, Уово обнаружил, что выбрать высоты для контрольных точек слишком сложно. Помогите Уово определить, существует ли последовательность вещественных чисел $$$b_1, \ldots, b_n$$$, удовлетворяющая всем ограничениям выше.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 66\,666$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 100\,000$$$).
$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x_i^-$$$, $$$x_i^+$$$ ($$$-10^8\le x_i^-\le x_i^+\le 10^8$$$), обозначающих нижнее и верхнее ограничение на $$$b_i$$$.
$$$i$$$-я из следующих $$$n-1$$$ строк содержит два целых числа $$$y_{i+1}^-$$$, $$$y_{i+1}^+$$$ ($$$-10^8\le y_{i+1}^-\le y_{i+1}^+\le 10^8$$$), обозначающих нижнее и верхнее ограничение на $$$b_{i+1}-b_i$$$.
$$$i$$$-я из следующих $$$n-2$$$ строк содержит два целых числа $$$z_{i+2}^-$$$, $$$z_{i+2}^+$$$ ($$$-10^8\le z_{i+2}^-\le z_{i+2}^+\le 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}$$$) не изменит ответ.
Для каждого набора входных данных, выведите YES, если существует последовательность $$$b_1,\ldots, b_n$$$, удовлетворяющая всем ограничениям. И NO иначе. Выводить саму последовательность $$$b_1,\ldots, b_n$$$ не требуется.
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
В первом наборе входных данных все $$$b_i$$$ принадлежат отрезку $$$[0,1]$$$. Из-за ограничения $$$1=y_2^-\le b_2-b_1\le y_2^+=1$$$, $$$b_2-b_1$$$ должно равняться $$$1$$$. Поэтому, должно выполняться $$$b_2=1$$$ и $$$b_1=0$$$. Потом, по $$$1=y_3^-\le b_3-b_2\le y_3^+=1$$$, $$$b_3$$$ равно $$$2$$$. Это приводит к противоречию с ограничением $$$b_3\le 1$$$. Поэтому, решения не существует.
Во втором наборе входных данных мы можем сделать все $$$b_i$$$ равными $$$0$$$.
В третьем наборе входных данных одно из возможных решений это $$$b_1=0$$$, $$$b_2=1/3$$$, $$$b_3=2/3$$$, $$$b_4=1$$$.
Название |
---|