Вычислительная геометрия

Лектор - Андрей Давыдов andrey.a.davydov@gmail.com

Домашние задания

Задание 1. Проверка принадлежности точки полигону

Дедлайн: 17.09

На вход N вершин полигона в формате (x, y) [abs(x), abs(y) <= 10^5] и M точек запроса. На выходе — M строк yes/no. Полигон всегда корректный, закрученный против часовой стрелки. Полигон считать замкнутым, т.е. для точек на границе ожидаемый ответ — yes.

input	output
3 (0, 0) (3, 0) (0, 2) 3 (0, 1) (1, 1) (2, 1)	yes yes no

Задание 2. Триангуляция монотонного полигона

Дедлайн: 1.10

На вход полигон в том же формате и с теми же ограничениями на координаты, что в первом задании. Гарантируется, что полигон монотонен относительно OX, закручен против часовой стрелки, и первая вершина в инпуте — самая левая. Требуется разбить его на треугольники. На выходе N-2 тройки индексов (номеров вершин полигона) — треугольники на соответствующих вершинах. Формат троек такой же как точек в инпуте, то есть (i, j, k). Треугольники должны быть закручены против часовой стрелки, среди возможных троек представляющих один и тот же треугольник нужно выбирать наименьшую лексикографически. Сами тройки могут идти в любом порядке. Вершины полигона нумеруются с 0.

Пример (неофициальный):

input	output
4 (0, 0) (1, 0) (1, 1) (0, 1)	(0, 1, 2) (0, 2, 3)