- Описание
- Отправленные решения
165. Уголки
Программист Василий рисует уголки на бесконечном клетчатом листке бумаги. Каждый уголок представляет из себя прямой угол, образованный двумя лучами, начинающимися в одном узле сетки, один из которых вертикален, а второй — горизонтален (лучи тоже являются частью уголка). Нарисовав $n$ уголков, Василий задумался — а верно ли, что эти уголки накрывают весь листок? Помогите ему ответить на этот вопрос.
Формат ввода
В первой строке число $n$ ($2 \le n \le 55\,555$) — количество уголков. В каждой из следующих $n$ строк — четыре числа $x_i$, $y_i$, $vertical\_direction_{i}$, $horizontal\_direction_{i}$. $x_i$, $y_i$ ($-1\,000\,000\,000 \le x_i, y_i \le 1\,000\,000\,000$) — координаты начала $i$-го уголка (обязательно целые числа). $vertical\_direction_{i}$ равен либо 1, если вертикальный луч $i$-го уголка направлен вверх, либо -1, если вниз. $horizontal\_direction_{i}$ равен либо 1, если горизонтальный луч $i$-го уголка направлен направо, либо -1, если налево.
Формат вывода
Нужно вывести либо YES, если уголки покрывают весь листок, либо NO, если нет.
Примечание
Нарисованная картинка может выглядеть так.
Ограничения
Ограничение времени
3 с
Ограничение памяти
256 МБ
Пример 1
4
0 0 1 -1
0 0 -1 1
0 0 1 1
0 0 -1 -1
YES
Пример 2
2
0 0 1 1
0 0 -1 -1
NO