Задача Метеоритный дождь

Описание

Вам была передана информация о надвигающемся метеоритном дожде. Также у Вас есть информация о возможных координатах точек падения метеоритов в случае, если они пройдут слои атмосферы. Вам необходимо определить, какие из метеоритов могут упасть на Ваше государство. Территория государства представляет собой выпуклый многоугольник, граница которого задана списком вершин в порядке обхода против часовой стрелки. Необходимо для множества координат точек падения определить, лежат ли они внутри государства. Точки, лежащие на границе государства, не считаются лежащими внутри. Возможно, что среди вершин, описывающих границу многоугольника, существует более двух, находящихся на некоторой прямой.

Формат входных данных

В первой строке файла находится целое число N (3 <= N <= 20 000) – количество вершин, описывающих границу многоугольника. В каждой из следующих N строк находится два числа, разделенные пробелом, описывающие координаты очередной точки границы. В следующей строке находится целое число M (1 <= M <= 20 000) – количество метеоритов.

В каждой из следующих M строк находится два числа, разделенные пробелом, описывающие координаты точки, для которой необходимо проверить условие задачи. Все координаты во входном файле – целые числа, по модулю не превосходящие 10^6.

Формат выходных данных

Файл должен содержать M строк, по одной строке на каждый метеорит. Если точка падения метеорита находится на территории Вашего государства, то строка должна содержать единственное слово YES, иначе – NO.