Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Многоугольник и точки

(Время: 1 сек. Память: 16 Мб Сложность: 51%)

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

Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа N и M – количество вершин многоугольника и количество точек соответственно (3 ≤ N ≤ 1000, 1 ≤ M ≤ 1000).

Каждая из последующих N строк содержит по два целых числа – координаты очередной вершины многоугольника. Вершины перечислены в порядке обхода, причём возможны варианты как «против часовой стрелки», так и «по часовой стрелке». Далее следуют M строк, содержащих список точек, заданных в аналогичном формате. Все координаты являются целыми числами и по модулю не превосходят 109.

Гарантируется, что многоугольник не имеет самопересечений, является строго выпуклым, и каждый его угол лежит в интервале от 0 до 180 градусов.

Выходные данные

В выходной файл OUTPUT.TXT для каждого запроса выведите в отдельной строке «Yes», если точка принадлежит многоугольнику или его границе, и «No» в противном случае.

Примеры

INPUT.TXTOUTPUT.TXT
14 3
1 1
1 -1
-1 -1
-1 1
0 0
0 1
0 2
Yes
Yes
No
23 1
1 0
1 1
0 0
0 1
No

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 Седьмая командная олимпиада
 A. Том и Джерри
 B. Таблица умножения
 C. Многословие
 D. Карты, числа, два заклинания
 E. Многоугольник и точки
 F. Вася и отрезки
 G. Игра в зачеркивание
 H. Очень длинный корень

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru