Огородження стада#11184

Огородження стада

1 секунда

128 мегабайтів

Дуже складна

Фермеру Джону потрібна ваша допомога, щоб визначити, де побудувати прямолінійний паркан для обмеження пересування його корів. Він розглянув кілька можливих варіантів розташування паркану і хоче визначити, які з них є допустимими. Паркан вважається допустимим, якщо всі корови знаходяться строго по один бік від нього; якщо хоча б одна корова лежить безпосередньо на паркані, такий паркан вважається недопустимим.

ФД задаватиме низку запитів про можливі розташування паркану. Для кожного запиту виведіть $Y E S$ , якщо відповідний паркан є допустимим, і $N O$ в іншому випадку.

Крім того, ФД час від часу може додавати нових корів до стада. З моменту додавання нової корови кожен наступний запит про паркан повинен враховувати й її: щоб паркан вважався допустимим, нова корова також повинна знаходитися по той самий бік паркану, що й усі інші корови.

Вхідні дані

У першому рядку містяться два цілих числа $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) і $q (1 \leq q \leq 1 0^{5})$ q~(1 \le q \le 10^5), що позначають початкову кількість корів у стаді та кількість запитів відповідно.

Наступні $n$ рядків описують початковий стан стада. Кожен рядок містить два розділених пробілом цілих числа $x$ і $y$ , що задають положення однієї корови.

Наступні $q$ рядків містять запити, які або додають нову корову до стада, або перевіряють допустимість паркану.

Запит вигляду "1 x y" означає, що до стада додається нова корова в точці $(x, y)$ .

Запит вигляду "2 A B C" означає, що ФД хоче перевірити паркан, заданий рівнянням $A x + B y = C$ Ax + By = C.

Всі положення корів різні протягом усього вхідного набору даних і задовольняють умові $- 1 0^{9} \leq x, y \leq 1 0^{9}$ -10^9 \le x, y \le 10^9. Параметри паркану задовольняють умовам $- 1 0^{9} \leq A, B \leq 1 0^{9}$ -10^9 \le A, B \le 10^9 і $- 1 0^{18} \leq C \leq 1 0^{18}$ -10^{18} \le C \le 10^{18}. Жоден запит про паркан не має $A = B = 0$ A = B = 0.

Вихідні дані

Для кожного запиту про паркан виведіть " $Y E S$ ", якщо паркан є допустимим, і " $N O$ " в іншому випадку.

Приклади

Пряма $2 x + 2 y = 3$ 2x + 2y = 3 спочатку залишає всіх $3$ корів по один бік від неї. Однак після додавання корови в точці $(1, 1)$ вона опиняється по інший бік паркану, тому паркан більше не є допустимим.

Пряма $y = 1$ y = 1 є недопустимою, оскільки корови в точках $(0, 1)$ і $(1, 1)$ лежать безпосередньо на ній.

Приклад 1