АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

16. Многоугольник

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

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

Исходные данные

В первой строке записано натуральное число N<=1000 - число вершин многоугольника.
В следующих N строках записаны по два целых числа xi и yi (-10000<=xi,yi<=10000), разделенных пробелом - координаты очередной вершины в порядке обхода.
В следующей строке записано натуральное число K - количество тестовых точек (1<=K<=100).
В следующих K строках записаны по два целых числа, разделённых пробелом - координаты очередной точки (также в диапазоне от -10000 до 10000).

Результат

Для каждой точки выведите в отдельной строке слово IN, если она лежит внутри многоугольника, и OUT - если снаружи.

Пример

Исходные данныеРезультат
4
3 0
2 3
6 5
0 5
2
1 4
3 2
IN
OUT

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Математика / Геометрия /
872. Triangle 16. 18. Монеты 11. Окружности 7. Отражения
Задачи с соревнований / Отборочные туры ВоГУ / Отборочный тур на ACM ICPC 2004 /
15. C - Факториалы 16.
Задачи с соревнований / Тренировки ВоГУ / Тренировка 29.10.08 /
16. 97. Прогрессия 19. Раскрытие скобок
Задачи с соревнований / Отборочные туры ВоГУ / ВГПУ отборочный тур 2014 /
179. 1 - Великая треугольная область 16. 292. 3 - Одностороннее движение 898. 4 - Языки 267. 5 - Муха - слон
Задачи с соревнований / Тренировки ВоГУ / Геометрия и не только /
89. C - Геодезия 16.
 
время генерации 0.14 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.