Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
sonic
Сообщений: n/a
#1

Обогнуть остров, выбрав кратчайший путь вокруг острова - C++

10.01.2008, 16:05. Просмотров 1499. Ответов 3
Метки нет (Все метки)

Во входном файле находятся: число N, задающее количество вершин многоугольника и далее координаты вершин многоугольника в виде списка x [0], y [0], x [1], y [1], . . . x[n-1], y [n-1] координат последовательных точек береговой линии острова.
Путешественники находятся в точке x [0], y [0]. Нужно обогнуть остров, выбрав кратчайший путь вокруг острова. Конечная точка должна совпадать с отправной точкой.
Очевидно, что путешественники должны двигаться по ломанной линии, отрезки которой соединяют точки береговой линии, так что, например для выпуклого многоугольника путь будет совпадать с береговой линией.
Написать программу, определяющую длину кратчайшего пути для любой фрмы острова, в том числе и для невыпуклого острова.

Помогите пожалуйста!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2008, 16:05     Обогнуть остров, выбрав кратчайший путь вокруг острова
Посмотрите здесь:
Кратчайший путь коня с++ C++
C++ Графы кратчайший путь !
Кратчайший путь в графе. C++
Найдите кратчайший путь в графе C++
Кратчайший путь в графе(Рекурсия) C++
C++ Найти кратчайший путь шахматного короля
C++ Как найти НЕ Кратчайший путь в графе ?
C++ Найти кратчайший путь из вершины u в вершину v
Как найти кратчайший путь в лабиринте? C++
Графы, расположить людей по билетам, кратчайший путь C++
C++ Кратчайший путь до какой-то координаты. Ошибка std::bad_alloc
Кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Гость
Сообщений: n/a
02.02.2008, 17:43     Обогнуть остров, выбрав кратчайший путь вокруг острова #2
мы тоже не можем решить ету задачу реши сам!
Михайло
112 / 112 / 6
Регистрация: 12.05.2010
Сообщений: 1,207
04.02.2008, 10:25     Обогнуть остров, выбрав кратчайший путь вокруг острова #3
Скорее всего, здесь что-то с условием либо я чего-то не понимаю...
Если заданы "координаты вершин многоугольника в виде списка координат последовательных точек береговой линии острова", то "обогнуть остров" можно только, пройдя вдоль всей береговой линии. Т. е. последовательно перемещаясь из точки (x[i],y[i]) в точку (x[i+1],y[i+1])...
Вот если бы координаты береговой линии были заданы в произвольном порядке, то здесь ещё можно было бы вести речь о какой-то оптимизации... Однако, тогда мы просто оптимизируем береговую линию, т. е. форму острова...
Таким образом, в условия задачи противоречит физике вещей...
Другое дело - транспортная задача (оптимизировать маршрут движения между N точками).
dmelvis
Сообщений: n/a
12.02.2008, 22:59     Обогнуть остров, выбрав кратчайший путь вокруг острова #4
По координатам можно вычислить угол наклона линии соединяющих ближайшую и следующую за ней точку берегового многоугольника. Надо решить как обходим остров по часовой или против часовой стрелки и исходя из этого оценивать по углам (если по часовой стрелке и линия к первой точке "правее" чем линия ко второй точке то первую точку исключаем и т.д.) По-моему, так можно решить.
Yandex
Объявления
12.02.2008, 22:59     Обогнуть остров, выбрав кратчайший путь вокруг острова
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru