Многоугольник и точки
(Время: 1 сек. Память: 16 Мб Сложность: 51%)
Дан выпуклый многоугольник и несколько точек. Для каждой точки необходимо определить, принадлежит ли она многоугольнику. Точки на границе многоугольника считаются принадлежащими ему.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и M – количество вершин многоугольника и количество точек соответственно (3 ≤ N ≤ 1000, 1 ≤ M ≤ 1000).
Каждая из последующих N строк содержит по два целых числа – координаты очередной вершины многоугольника. Вершины перечислены в порядке обхода, причём возможны варианты как «против часовой стрелки», так и «по часовой стрелке». Далее следуют M строк, содержащих список точек, заданных в аналогичном формате. Все координаты являются целыми числами и по модулю не превосходят 109.
Гарантируется, что многоугольник не имеет самопересечений, является строго выпуклым, и каждый его угол лежит в интервале от 0 до 180 градусов.
Выходные данные
В выходной файл OUTPUT.TXT для каждого запроса выведите в отдельной строке «Yes», если точка принадлежит многоугольнику или его границе, и «No» в противном случае.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 3
1 1
1 -1
-1 -1
-1 1
0 0
0 1
0 2
| Yes
Yes
No |
| 2 | 3 1
1 0
1 1
0 0
0 1 | No |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
