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

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

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

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

10.01.2008, 16:05. Просмотров 1508. Ответов 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++
Такая задача: Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь из вершины s в вершину t. ...

Кратчайший путь коня с++ - C++
помогите пожалуйста написать алгоритм кротчайшего пути коня на шахматной доске из А в Б

Кратчайший путь паука до мухи - C++
Есть задача (https://www.e-olymp.com/ru/problems/74): Паук и муха - 2 В пустой прямоугольной комнате длины А, ширины В и высоты С...

Кратчайший путь в графе(Рекурсия) - C++
Я реализовал программу с помощью алгоритма флойда.Препод придрался к тому что я реализовал без рекурсии. Помогите изменить прогу под...

Найдите кратчайший путь в графе - C++
Создайте граф согласно своего варианта в среде С + +, длины путей задайте самостоятельно, найдите кратчайший путь в графе, используя...

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

Как найти НЕ Кратчайший путь в графе ? - C++
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан списком смежности типа: 5 1 1 2 3...

Найти самый кратчайший путь в массиве - C++
У меня есть динамический массив в котором количество строк задаётся при выполнении программы, а количество строк неизменно и равно 3. Мне...

Как найти кратчайший путь в лабиринте? - C++
Чтобы найти кратчайший путь в лабиринте использую волновой алгоритм, его сделал, но вот кратчайший путь не получается восстановить. ...

Найти кратчайший путь шахматного короля - C++
Здравствуйте, имеется задача: Есть шахматное поле NxM N, M ≤ 10^9 На шахматном поле отмечено два прямоугольника размерами не менее...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
12.02.2008, 22:59
Ответ Создать тему
Опции темы

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