Методы программирования

Министерство образования и науки Российской Федерации

Новосибирский государственный технический университет

Кафедра прикладной математики

Расчетно-графическое задание

по практикуму на ЭВМ:

методы программирования

Факультет: ПМИ

Группа: ПМ-65

Студент: Пешкичева А.А.

Преподаватель: Хиценко В.П.

Вариант:41

Новосибирск

2016

1.Условия задачи

Построить множество всех различных выпуклых четырехугольников с вершинами в заданном множестве точек на плоскости.

2.Анализ задачи 

Дано: количество точек n<=10.

sx={ sx[i], где sx[i] ∈R x-координата точки}

sy={ sy[i], где sy[i] ∈R у-координата точки}

Результат:

Все возможные выпуклые четырехугольники, найденные в данной области на плоскости.

В Данном случае выходными данными являются - номер найденного четырехугольника: номера вершин полученного многоугольника. Если таких многоугольников нет, то выводиться запись «Нет выпуклых четырехугольников»

Метод решения:

Подзадачи:

1. Организация перебора всех точек области без повторений. Перебирать точки нужно четверками, при этом все четверки являются различными;

Вершины 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)