Основы программирования

Задача построения триангуляции Делоне является одной из базовых в вычислительной геометрии. К ней сводятся многие другие задачи, она широко используется в машинной графике и геоинформационных системах для моделирования поверхностей и решения пространственных задач.

Промасштабировать и построить на экране фигуру, заданную в файле списком координат ее вершин.

Среда разработки программного обеспечения (english. IDE, Integrated development environment) на языке Pascal для ОС DOS. Компиллятор и текстовый редактор. Pascal, первоначально разработанный Николаусом Виртом в 1970, был значительно расширен фирмой Borland и приобрел название Turbo Pascal (позднее Borland).

Задано регулярное выражение r = (a|b|c)*bc.
Входной алфавит ∑= {a, b, c}.
Написать программу, распознающую строки, соответствующие данному регулярному выражению.
(Соответствуют: abbbabcbbcabc, bc, abc, bbbc, abcbc, cbc, aabbccbc. Не соответствуют: abccba, bca, abcbcc).
Использовать теории регулярных выражений и конечных автоматов (КА):
1. Для заданного регулярного выражения построить соответствующий ему КА;
2. Если автомат, полученный в предыдущем пункте, недетерминированный, то преобразовать его в ДКА;
3. Используя ДКА, написать программу-распознаватель.

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

Алгоритм триангуляции, примененный при написании данной программы, описан в заметках Задача триангуляции многоугольника и Определение направления обхода многоугольника.
Реализация на С++.

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