Задача Веник

@RahaMilopNo · Регистрация: 16.12.2019

Студворк — интернет-сервис помощи студентам

На делянке расположены деревья. Количество деревьев известно и
равно количеству строк во входном файле. Количество строк не
превышает 25.
Все деревья связаны натянутой верёвкой, образуя цикл. Верёвка не
может пересекать себя ни в какой точке. Толщину деревьев можно считать равной нулю — таким образом, деревья можно рассматривать как
точки на плоскости.
Следует найти наименьший и наибольший периметр фигуры,
которая может получиться.
Пример входных данных:

Code
1
2
3
4
5
6
7
8
 -34.57666 -41.04938
 12.11894 87.89307
 -67.79820 -82.89454
 -25.37782 -57.23356
 6.61201 85.79871
 -81.43984 -9.48410
 43.39703 -2.14410
 -35.63594 13.70402

В данном случае минимальный периметр фигуры будет равен
466,1092, а максимальный — 786,4055.

@DmitriyLutsenko · 25.04.2024, 15:12

Сообщение от RahaMilopNo

-34.57666 -41.04938
12.11894 87.89307
-67.79820 -82.89454
-25.37782 -57.23356
6.61201 85.79871
-81.43984 -9.48410
43.39703 -2.14410
-35.63594 13.70402

В каждой строке координаты по (x; y), правильно ?

@RahaMilopNo · 25.04.2024, 15:44 **[ТС]**

Сообщение от DmitriyLutsenko

В каждой строке координаты по (x; y), правильно ?

Правильно)

@Ewlampiy · 25.04.2024, 16:54

Это про полный перебор или про что то более интеллектуальное?

Случаи касания вместо пересечения могут быть или они заранее исключены в исходных данных?

@DmitriyLutsenko · 25.04.2024, 16:56

Это скорее всего задача коммивояжера, завязанная на динамическом программировании, причем требуется оптимизированный вариант(когда пути не пересекаются) )

@vcrop · 26.04.2024, 01:04

Сообщение от DmitriyLutsenko

причем требуется оптимизированный вариант(когда пути не пересекаются)

Предложи.

@DmitriyLutsenko · 26.04.2024, 08:24

Сообщение от vcrop

Предложи.

Предлагаю тебе помочь с кодом для решения данной задачи ТС

Пойдет?

Давай проясним такую вещь:
Я обозначил возможную сферу вопроса. Это похоже на задачу коммивояжера? Похоже.
"Оптимизированный" означает, что сам граф не должен иметь перекруток, а не то, что сам код должен выполняться за 0.00001мс и занимать всего 1 Байт в памяти.

Я давно таких задач не решал, но помню, что у меня в студенческие годы было очень похожее задание.

@vcrop · 26.04.2024, 14:58

Сообщение от DmitriyLutsenko

но помню, что у меня в студенческие годы было очень похожее задание.

Решаема задача коммивояжера с double типом в условии?

@DmitriyLutsenko · 26.04.2024, 15:35

Сообщение от vcrop

Решаема задача коммивояжера с double типом в условии?

Решаема(длина ребер же может быть дробным числом). Но над реализацией надо думать.

Я говорю пока на вскидку.

Отсортировать точки по x или y координате. Расположение в пространстве не поменяется, но мы хотя бы определим стартовую точку. (0, 1, 2, 3, 4 и тд.)
вычислить длину ребер от одной точки до другой.
Составить матрицу с длинами этих точек.
Отдельно разработать условие добавления точки, при которой новое ребро не будет пересекаться с другими(уже построенными ребрами).
Как найти периметр? Можно сразу прибавлять длины ребер, а можно сначала сформировать список (Считай, неотрывной путь ) от начальной вершины до всех остальных по мере их добавления ([0, 1, 3, 2, 4, 0]) - В случае нахождения фигуры с большим периметром мы найдем пути, в котором будут учтены все точки и просто возьмем длины ребер по номеру точки из матрицы, не

А теперь скажи, товарищ, как бы ты сам решал такую задачу?
Я свой ход мыслей написал, хотелось бы услышать мнение старожила нашего форума

@RahaMilopNo · 26.04.2024, 16:25 **[ТС]**

У меня к сожалению вообще нет понимания как решать данную задачу(

@RahaMilopNo · 26.04.2024, 17:24 **[ТС]**

К заданию прилагается файл, не знаю для чего и как поможет.
test1.rar

@RahaMilopNo · 26.04.2024, 19:08 **[ТС]**

Сообщение от Ewlampiy

Это про полный перебор или про что то более интеллектуальное?
Случаи касания вместо пересечения могут быть или они заранее исключены в исходных данных?

Честно, совсем не понимаю задание

@Ewlampiy · 26.04.2024, 21:25

Сообщение от RahaMilopNo

Честно, совсем не понимаю задание

А оно откуда если не секрет? Оно явно и не для учебы и не для тестирования, это с какого то челенжа

Даже просто проверка пересекаются ли два отрезка - перебор для "начинающих"

@RahaMilopNo · 27.04.2024, 22:28 **[ТС]**

Сообщение от Ewlampiy

А оно откуда если не секрет? Оно явно и не для учебы и не для тестирования, это с какого то челенжа

С учебы, задание на контрольную точку

@mavapo · 23.05.2024, 12:23

Думаю это задача на математическое решение. Конкретно на анализ и выработку математических подходов очень сильно ограничивающих варианты расчета. После этого можно будет код писать. А так, в лоб, задача спокойно решается для ваших 8 точек просто перебором. Для большего количества точек, особенно для 25,уже не решается из-за комбинаторного взрыва. До скончания времен считать будет.

@mavapo · 24.05.2024, 09:01

Поскольку изучаю яву, в качестве разминки написал реализацию простым перебором. Это не решение задачи из темы. просто реализация перебора для ровно 8 точек из задания. Если что, претензии не принимаются. Написано прямолинейно, не структурировано и с тупейшими самопальными переборами. Так писать конечно же нельзя. Просто фу так писать.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@Ewlampiy 156 / 62 / 16 Регистрация: 12.12.2023 Сообщений: 389
	25.04.2024, 16:54
	Это про полный перебор или про что то более интеллектуальное? Случаи касания вместо пересечения могут быть или они заранее исключены в исходных данных? 0

@DmitriyLutsenko 75 / 61 / 16 Регистрация: 13.07.2020 Сообщений: 258
	25.04.2024, 16:56
	Это скорее всего задача коммивояжера, завязанная на динамическом программировании, причем требуется оптимизированный вариант(когда пути не пересекаются) ) 0

@RahaMilopNo 67 / 40 / 28 Регистрация: 16.12.2019 Сообщений: 259
	26.04.2024, 16:25 [ТС]
	У меня к сожалению вообще нет понимания как решать данную задачу( 0

@RahaMilopNo 67 / 40 / 28 Регистрация: 16.12.2019 Сообщений: 259
	26.04.2024, 17:24 [ТС]
	К заданию прилагается файл, не знаю для чего и как поможет. test1.rar 0

@mavapo 1 / 1 / 0 Регистрация: 01.03.2024 Сообщений: 16
	23.05.2024, 12:23
	Думаю это задача на математическое решение. Конкретно на анализ и выработку математических подходов очень сильно ограничивающих варианты расчета. После этого можно будет код писать. А так, в лоб, задача спокойно решается для ваших 8 точек просто перебором. Для большего количества точек, особенно для 25,уже не решается из-за комбинаторного взрыва. До скончания времен считать будет. 0