Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Fencing the Herd

Фермер Джон нуждается в Вашей помощи. Он решил построить изгородь в форме прямой, чтобы ограничить движение своих коров. Он рассматривает несколько вариантов размещения изгороди и с Вашей помощью хочет определить наиболее подходящий. Подходящим считается вариант, когда все коровы находятся по одну сторону изгороди. Изгородь не считается подходящей, если хоть одна корова расположена на изгороди. ФД будет задавать Вам вопросы про варианты изгороди, на которые Вы должны отвечать YES, если изгородь подходит и NO, в противном случае.
 
Кроме того, ФД может добавить новых коров в стадо. С того момента, как корова добавлена, она должна быть по одну сторону от изгороди со всеми другими коровами.
 
INPUT FORMAT: 
Первая строка ввода содержит N (1 <= N <= 100,000) and Q (1 <= Q <= 100,000) разделённые одним пробелом. Это, соответственно, начальное количество коров в стаде и количество запросов.
 
Следующие N строк описывают начальное положение стада. Каждая строка содержит два целых числа x и y (разделённые пробелом), представляющие позицию очередной коровы.
 
Оставшиеся Q строк содержат запросы, либо добавляющие новую корову в стадо, либо проверяющие изгородь на применимость. Строка вида 1 x y означает, что новая корова добавляется в стадо на позицию x y. Строка вида 2 A B C означает, что ФД хочет проверить изгородь, описываемую прямой Ax+By=C
 
Все позиции коров уникальны и (-10^9 <= x, y <= 10^9). Кроме того, -10^9 <= A, B <= 10^9 and -10^18 <= C <= 10^18. Никогда не будет изгороди с A = B = 0.
 
OUTPUT FORMAT: 
Для каждой изгороди выведите YES, если она подходит и NO, в противном случае.

Ввод Вывод
3 4
0 0
0 1
1 0
2 2 2 3
1 1 1
2 2 2 3
2 0 1 1
YES
NO
NO


Прямая 2x + 2y = 3 оставляет начальные 3 коровы по одну сторону. Однако корова (1,1) на другой стороне, поэтому после её добавления такая изгородь уже не подходит. Прямая Y=1 не подходит, поскольку коровы (0,1) и (1,1) находятся на ней.
 
Предупреждение: ввод-вывод для этой задачи очень большой. В С++ можно использовать scanf или ios_base::sync_with_stdio(false). В Java надо не использовать java.util.Scanner. Не делайте flush вывода (например? используя std::endl) после каждого запроса.


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

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


Нет

Примечание учителя: