Методы программирования
Автор: Anastasia Peshkicheva • Февраль 9, 2022 • Контрольная работа • 3,463 Слов (14 Страниц) • 203 Просмотры
Министерство образования и науки Российской Федерации
Новосибирский государственный технический университет
Кафедра прикладной математики
Расчетно-графическое задание
по практикуму на ЭВМ:
методы программирования
Факультет: ПМИ
Группа: ПМ-65
Студент: Пешкичева А.А.
Преподаватель: Хиценко В.П.
Вариант:41
Новосибирск
2016
1.Условия задачи
Построить множество всех различных выпуклых четырехугольников с вершинами в заданном множестве точек на плоскости.
2.Анализ задачи
Дано: количество точек n<=10.
sx={ sx[i], где sx[i] ∈R x-координата точки}
sy={ sy[i], где sy[i] ∈R у-координата точки}
Результат:
Все возможные выпуклые четырехугольники, найденные в данной области на плоскости.
В Данном случае выходными данными являются - номер найденного четырехугольника: номера вершин полученного многоугольника. Если таких многоугольников нет, то выводиться запись «Нет выпуклых четырехугольников»
Метод решения:
Подзадачи:
- Организация перебора всех точек области без повторений. Перебирать точки нужно четверками, при этом все четверки являются различными;
Вершины a-b-c-d являются номерами точек, стоящих в вершинах четырехугольника и идущих по порядку по часовой стрелке или против нее:
[pic 1]
2) Для трех выбранных точек нужно ввести проверку на их принадлежность одной прямой, сокращая при этом количество перебираемых вариантов;
4) Для четырех выбранных точек определить их взаимное положение относительно друг друга. Для четырехугольника существует три таких варианта, два из которых нужно свести к третьему;
5) После этого четыре точки нужно проверить на принадлежность вершинам выпуклого четырехугольника. Алгоритм описан ниже:
Для определения выпуклости четырехугольника будем исходить из того, что если в четырехугольнике провести диагональ, то не соединенные вершины будут лежать по разные стороны от проведенной прямой. То же самое нужно проделать и для другой диагонали. Получаем три случая (см. рисунок ниже). Как видно из рисунка: наиболее простой способ решения поставленной задачи – это следующая проверка:
[pic 2]
где [pic 3]- это точка пересечения следующих прямых: диагонали и или соответственно. В самом деле, если точки лежали по разные стороны от диагонали, то одна из разностей будет меньше нуля. Следует заметить, что данная проверка верна и для вырожденного четырехугольника, т.е. у которого одна из точек лежит на самой диагонали. В этом случае, выше описанная формула примет значение равно нулю, а значит выражение будет неверно.
Теперь вернемся ко второму и третьему случаю: т.е. когда точки образуют диагональ, параллельную одной из осей координат. Во втором случае нам вместо придется в вышеописанную формулу. Но при этом для обоих случаев нам не нужно будет вычислять и, т.к. они будут равны соответствующим координатам точек, образующих диагональ.
[pic 4]
k=0
a=0
Повторять
b=a+1
Повторять
c=b+1
Повторять
Если a, b, c не лежат на одной прямой, тогда
d=c+1
Повторять
Если , тогда
k=k+1
Вывести (k:abcd)
Если , тогда
k=k+1
Вывести (k:acbd)
Если , тогда
k=k+1
Вывести (k:abdc)
...