Задача 16.
На плоскости задан граф с N вершинами. Количество ребер, соединенных с каждой вершиной, равно 3.
Пример:
Пусть вершины X,Y и Z являются соседями вершины Т. Будем считать, что Y левый, а Z -правый сосед вершины Т относительно вершины X, если ориентированный угол XTZ меньше ориентированного угла XTY (положительным будем считать направление против часовой стрелки). Например вершина Е является правым соседом вершины Н относительно А, а G - левым, поскольку ориентированный угол АНЕ меньше ориентированного угла AHG. (Ребра считаются отрезками).
Составьте программу, которая:
1. Вводит координаты вершин графа и его ребра и рисует граф на экране компьютера, производя при этом подходящее масштабирование(Ребра выводятся как отрезки).
2. Пусть заданы две начальные соседние вершины X0 и X1 и последовательность вида LLRRL... Тогда программа находит путь на графе X0 X1 X2...Xn для вершин которого выполнено:
-первые два являются заданными X0 и X1
-Xi+1 является левым или правым соседом Xi относительно Xi-1 в зависимости от заданной последовательности, при том L означает левый, а R -правый.
Пример:В заданном графе пусть даны начальные вершины А и H и последовательность LRRLLR. Тогда программа должна найти путь AHGFEDCB.
3. Рисует на экране путь, найденный в п.2.
4. Пусть даны начальная и конечная вершина. Программа должна найти путь, проходящий через минимальное число вершин, вывести его на экран и найти 2 первые вершины и управляющую последовательность для этого пути, как определено в п.2.
|
