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

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

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

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

22.06.2013, 14:59. Просмотров 485. Ответов 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++
На плоскости заданы N точек своими декартовыми координатами. Расположить эти точки в таком порядке, чтобы они образовывали вершины...

Распределить камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным - C++
Доброго времени суток! Требуется программу, которая распределит камни в две кучи так, чтобы модуль разности весов этих двух куч был...

Переписать все элементы из этих массивов в массив С так, чтобы массив С был упорядоченным - C++
Даны два упорядоченных целочисленных массива: А, содержащий n1 элементов и В из n2 элементов. Переписать все элементы из этих массивов в ...

Соединить точки на плоскости замкнутой ломаной линией без самопересечений - Pascal ABC
Доброго времени суток. Задача такая : Соединить точки на плоскости замкнутой ломаной линией без самопересечений. Дошел до момента,...

Набить рюкзак этими предметами так, чтобы их общий вес был не менее m и при этом был минимальным - Pascal
Для решения одного задания мне нужно решить следующую подзадачу. Суть такова: Есть рюкзак бесконечной вместимости и n предметов. Нужно...

Соединить 4 точки ломаной линией без пересечений - C#
Доброго времени суток, вопрос заключается в следующем: Пользователь вводит координаты 4-х точек на плоскости, необходимо максимально...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Lepidoptera
0 / 0 / 0
Регистрация: 03.05.2014
Сообщений: 2
04.01.2016, 01:30 #2
Если актуально - я написал эту прогу когда-то на java. Суть - выбрать минимаксные значения координат по x и y, далее: перейти в полярные координаты, ввести угол фи и радиус-вектор. На 1 точку у Вас появляется 4 координаты. Берите и варьируйте ими. Алгоритм прост - движетесь по плоскости по восходящему углу и по нисходящей координате. И так меняете свое движение при наскакивании на минимаксные значения по x или y. Ну а далее - сами. Все просто. Если надо - сброшу на гите ссылку
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.01.2016, 01:30
Привет! Вот еще темы с ответами:

Соединить точки (по координатам из таблицы) ломаной линией - Lazarus
Дана таблица с координатами (х, у) семи точек. Изобразить их на рисунке и по выбору пользователя либо слева-направо, либо снизу-вверх, либо...

Ввести с клавиатуры строку в несколько точек и преобразовать её так, чтобы после каждой точки был пробел - Assembler
Задача заключается в том, чтобы ввести с клавиатуры строку, содержащую несколько точек и преобразовать её так, чтобы после каждой точки был...

Преобразовать строку так, чтобы после каждой точки был пробел, и следующая встречающаяся буква была прописная. - Assembler
Задана строка минимум 30 любых отображаемых символов, содержащая несколько точек. Преобразовать строку так, чтобы после каждой точки был...

Вставить одномерный массив в двумерный массив так, чтобы второй столбец был отсортирован по убыванию - Pascal
Помогите пожалуйста решить задачку: Вставить в качестве новой строки одномерный массив В в двумерный массив А так, чтобы второй столбец...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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