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

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

Войти
Регистрация
Восстановить пароль
 
d_gatar
0 / 0 / 0
Регистрация: 20.05.2013
Сообщений: 2
#1

Массив: Соединить точки замкнутой самонепересекающейся ломаной так, чтобы периметр полученного многоугольника был минимальным - C++

22.06.2013, 14:59. Просмотров 476. Ответов 1
Метки нет (Все метки)

Здравствуйте!! Такая проблема, не могу придумать алгоритм для решения следующей задачи, прощу подскажите, у кого есть какие идеи: В декартовой системе координат заданы координаты N точек. Требуется соединить их замкнутой самонепересекающейся ломаной так, чтобы периметр полученного многоугольника был минимальным.
INPUT – файл problem.in, в котором на первой строчке стоит число точек N, на последующих N строчках пары координат X_i,Y_i через пробел.
OUTPUT – файл problem.out, в котором на первой строчке выводится периметр многоугольника, на последующих N строчках выводятся номера точек в порядке их соединения.
Буду очень благодарен!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.06.2013, 14:59     Массив: Соединить точки замкнутой самонепересекающейся ломаной так, чтобы периметр полученного многоугольника был минимальным
Посмотрите здесь:
Даны точки на плоскости: расположить их так, чтобы они образовывали вершины выпуклого многоугольника C++
Распределить камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным C++
C++ Переписать все элементы из этих массивов в массив С так, чтобы массив С был упорядоченным
C++ Продумать и задать входные данные так, чтобы был 4-5 альтернатив
C++ Переделать программу так, чтобы каждый из кейсов был подключаемым модулем
В выражении расставить знаки так, чтобы результат вычислений был равен 35 C++
C++ Отредактировать текст так, чтобы между словами был ровно один пробел
Отредактировать текст так, чтобы между словами был ровно один пробел C++
C++ Преобразовать строку так, чтобы между словами был ровно один пробел
C++ Периметр многоугольника
C++ Дописать программу так, чтобы в массив вводились как целые числа так и вещественные

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Lepidoptera
0 / 0 / 0
Регистрация: 03.05.2014
Сообщений: 2
04.01.2016, 01:30     Массив: Соединить точки замкнутой самонепересекающейся ломаной так, чтобы периметр полученного многоугольника был минимальным #2
Если актуально - я написал эту прогу когда-то на java. Суть - выбрать минимаксные значения координат по x и y, далее: перейти в полярные координаты, ввести угол фи и радиус-вектор. На 1 точку у Вас появляется 4 координаты. Берите и варьируйте ими. Алгоритм прост - движетесь по плоскости по восходящему углу и по нисходящей координате. И так меняете свое движение при наскакивании на минимаксные значения по x или y. Ну а далее - сами. Все просто. Если надо - сброшу на гите ссылку
Yandex
Объявления
04.01.2016, 01:30     Массив: Соединить точки замкнутой самонепересекающейся ломаной так, чтобы периметр полученного многоугольника был минимальным
Ответ Создать тему
Опции темы

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