Задача: Fencing the Herd
Фермер Джон нуждается в вашей помощи. Он решил построить изгородь в форме прямой, чтобы ограничить движение своих коров. Он рассматривает несколько вариантов размещения изгороди и с вашей помощью хочет определить наиболее подходящий. Подходящим считается вариант, когда все коровы находятся по одну сторону изгороди. Изгородь не считается подходящей, если хоть одна корова расположена на изгороди. ФД будет задавать вам вопросы про варианты изгороди, на которые вы должны отвечать YES, если изгородь подходит и NO, в противном случае.
Кроме того, ФД может добавить новых коров в стадо. С того момента, как корова добавлена, она должна быть по одну сторону от изгороди со всеми другими коровами.
Входные данные
Первая строка ввода содержит N (1 <= N <= 100000) и Q (1 <= Q <= 100000) разделённые одним пробелом. Это, соответственно, начальное количество коров в стаде и количество запросов.
Следующие N строк описывают начальное положение стада. Каждая строка содержит два целых числа x и x (разделённые пробелом), представляющие позицию очередной коровы.
Оставшиеся Q строк содержат запросы, либо добавляющие новую корову в стадо, либо проверяющие изгородь на применимость. Строка вида 1 x y означает, что новая корова добавляется в стадо на позицию x y. Строка вида 2 A B C означает, что ФД хочет проверить изгородь, описываемую прямой Ax+By=C.
Все позиции коров уникальны (-109 <= x, x <= 109). Кроме того, -109 <= A, B <= 109 и -1018 <= C <= 1018. Никогда не будет изгороди с A = B = 0.
Выходные данные
Для каждой изгороди выведите
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) после каждого запроса.
Ваш ответ: