Олимпиадный тренинг

Задача . C. Места для селфи

Задача

Темы: Бинарный поиск геометрия математика Структуры данных *1400

Вселенная представляет собой координатную плоскость. На ней проложено $n$ космических трасс, каждая из которых представляет собой прямую $y=kx$, проходящую через начало координат $(0, 0)$. Также там есть $m$ астероидных поясов, которые представляют собой параболы ветвями вверх, их можно представить как графики функций $y=ax^2+bx+c$, где $a > 0$.

Вы хотите сфотографировать каждую параболу. Для этого для каждой параболы вам нужно выбрать прямую, которая не пересекается с этой параболой и не касается её. Вы можете выбирать одну и ту же прямую для нескольких парабол. Найдите для каждой параболы такую прямую или определите, что её нет.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке содержится одно число $t$ ($1 \le t \le 10^4$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора даны $2$ целых числа $n$ и $m$ ($1 \le n, m \le 10^5$) — количество прямых и парабол соответственно.

Далее в $n$ строках содержится по одному целому числу $k$ ($|k| \le 10^8$) — коэффициенты уравнений прямых $y=kx$, описывающих прямые. Прямые могут совпадать, $k$ может быть равно $0$.

Далее в $m$ строках содержится по $3$ целых числа $a$, $b$ и $c$ ($a, |b|, |c| \le 10^8$, $a > 0$) — коэффициенты уравнений парабол $ax^2+bx+c$. Параболы могут совпадать.

Гарантируется, что сумма $n$ по всем наборам не превосходит $10^5$ и сумма $m$ по всем наборам также не превосходит $10^5$.

Выходные данные

Для каждого набора входных данных выведите ответ для каждой параболы в данном порядке. Если в данном наборе есть прямая, не пересекающаяся с данной параболой и не касающаяся ее, выведите сначала в отдельной строке слово «YES», а далее в отдельной строке число $k$ — коэффициент этой прямой. Если таких прямых несколько, выведите любую из них. Если же искомой прямой нет, выведите одно слово «NO».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пустые строки в выводе в примере даны только для наглядности, вам их выводить необязательно (но можно).

Примечание

В первом наборе входных данных обе параболы не пересекаются с единственной данной прямой $y=1\cdot x$, поэтому ответом будет два числа $1$.

$\text{[math]}$

Во втором наборе прямая $y=x$ и парабола $2x^2+5x+1$ пересекаются, а также прямая $y=4x$ и парабола $x^2+2x+1$ касаются, поэтому эти пары не удовлетворяют условию. Значит, для первой параболы ответом будет $1$ ($y=1x$), а для второй параболы — $4$.

$\text{[math]}$

В третьем тестовом наборе прямая и парабола пересекаются, поэтому ответ — «NO».

Примеры

№	Входные данные	Выходные данные
1	5 1 2 1 1 -1 2 1 -1 3 2 2 1 4 1 2 1 2 5 1 1 1 0 1 0 0 1 1 100000000 100000000 100000000 100000000 2 3 0 2 2 2 1 1 -2 1 1 -2 -1	YES 1 YES 1 YES 1 YES 4 NO YES 100000000 YES 0 NO NO

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет