Числа. Точки на плоскости., N точек на плоскости, перестановки N чис Опции

[zetsokol]

Вот дали задачи на контрольную. Помогите кто чем может.

1. N точек на плоскости заданы своими координатами. Найти порядок, в котором можно соединить эти точки, чтобы получился N-угольник (т.е. не было бы пересечений сторон).

2.Построить алгоритм, выдающий без повторений все перестановки N чисел.

[Altair]

1. N точек на плоскости заданы своими координатами. Найти порядок, в котором можно соединить эти точки, чтобы получился N-угольник (т.е. не было бы пересечений сторон).

Представим множество точек на плоскости.

Теперь проведем триангуляцию

После этого у нас получилось не что иное как связанный граф.
Создаем для него матрицу смежности например (при этом запоминая, номера вершин какой точке соотвествуют).
После получаем задачу Эйлерова пути в чистом виде:
поиск цепи в графе, которая содержит все вершины и ребра в 1 экземпляре.

FAQ- >Эйлеров цикл в графе.