Однажды морж-профессор Платон задал студентам-программистам следующую лабораторную работу.
В лабораторной работе требовалось реализовать такую структуру данных, которая поддерживала бы выпуклую оболочку на некотором множестве точек S. На вход программе подавалось q запросов двух типов:
1. Добавить точку с координатами (x, y) во множество S. Заметьте, что при этом выпуклая оболочка множества S могла измениться, а могла остаться прежней.
2. Сказать, принадлежит ли точка с координатами (x, y) области, ограниченной выпуклой оболочкой, включая границу.
Все студенты справились с заданием. А справитесь ли с ним Вы?
Выходные данные
На каждый запрос второго типа выведите по одной строке, содержащей "YES", если точка лежит внутри выпуклой оболочки или на ее границе, и "NO" в противном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
1 0 0
1 2 0
1 2 2
2 1 0
1 0 2
2 1 1
2 2 1
2 20 -1
|
YES
YES
YES
NO
|