Нaйти местo из которого спичечная конструкция сгoрит зa нaименьшее врeмя

@MonstrTraf · Регистрация: 13.03.2019

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

Здравствуйте, формучане, вот такая головоломка мне попалась) Вообще не вдупляю что по чем, заранее благодарю за любую помощь

На вхoд подаeтся числo - количeство спичeк. И для каждoй спички указываются кoординаты начaла спички, коoрдинаты кoнца спички и врeмя еe горeния. В полyчившейся кoнструкции нужнo нaйти такоe местo, в котороe eсли пyстить oгонь, oна сгoрит зa нaименьшее врeмя и соoтветственно вывeсти полyчившееся врeмя. Огoнь движeтся равнoмерно, eсли oн дoходит дo развeтвления, тo идет вo всe стoроны. Грyбo гoворя, вeдет сeбя как огoнь.
Вoт тeст нa кoторoм будeт провeряться , там 16 спичeк, a в рeзультате дoлжно выйти 4.5 сeкунд

@Krokodil9798 · 13.03.2019, 17:25

1) Вам нужно найти центр масс "модели". В этом Вам поможет просто банальная сумма всех координат и деление итоговой "точки" на общее количество.
2) Потом нужно "перенести" (спроектировать) эту точку на ближайшую спичку.
3) Следующим шагом найдите наиболее отдалённую точку от центра масс.
4) Затем постройте кратчайший путь от центра масс до наиболее отдалённой точки.
5) В итоге, у Вас должно быть, например, в стеке, спички, по которым можно достичь центра масс от наиболее отдалённой точки.
6) Просуммируйте длину каждой спички, составляющей путь - так Вы узнаете длину цепи (s).
7) t(время) = s(расстояние) / v(скорость).

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

Вообще не вдупляю что по чем

P.S. Советую обходиться без жаргона в своей речи, а тем более в письме.

@MonstrTraf · 13.03.2019, 18:28 **[ТС]**

А может кто нибудь написать как это на С++ будет выглядеть? Я сути не понимаю...

@Krokodil9798 · 13.03.2019, 18:38

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

Я сути не понимаю...

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

@MonstrTraf · 13.03.2019, 18:53 **[ТС]**

Когда есть код я могу его прогнать по пунктам и в итоге догоню что к чему, так гораздо легче

@MonstrTraf · 15.03.2019, 17:51 **[ТС]**

UPP

@Krokodil9798 · 15.03.2019, 19:16

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

UPP

За Вас думать никто не будет. Берите, разбирайтесь с алгоритмом и наработки кода в студию. Тогда поможем

@outoftime · 16.03.2019, 02:09

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

Вам нужно найти центр масс "модели"

Позволю себе не согласиться. Дело в том что не известно под каким углом спички находятся друг к другу (если координаты в 2мерной системе координат).

Одномерный случай банальный и не интересный.

Выскажу мысли по поводу 2мерного. Мне кажется надо строить графф, где узлами будут точки пересечения и концы спичек. В этом случае надо будет найди вершину с минимальным расстоянием к дальней вершине. После этого бинарным поиском двигаться по каждому ребру выходящему из данной вершины и проверять будет ли расстояние в данной точке на ребре меньше нежели если бы мы подожгли вершину.

Добавлено через 49 секунд

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

Вoт тeст нa кoторoм будeт провeряться

Не красиво с вашей стороны обманывать людей. О том что предоставите тестовые данные написали, а данных не предоставили.

@MonstrTraf · 24.04.2019, 15:33 **[ТС]**

А если в графе циклы, как перебирать все возможные варианты?

@Kuzia domovenok · 24.04.2019, 16:20

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

1) Вам нужно найти центр масс "модели". В этом Вам поможет просто банальная сумма всех координат и деление итоговой "точки" на общее количество.

задача скорее на пути и графы, чем на центр масс. от расположения массы тут ничего не зависит, а вот от их сочленений таки да.

@Kuzia domovenok · 25.04.2019, 01:46

MonstrTraf, попробуй применить алгоритм Флойда

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@MonstrTraf 0 / 1 / 0 Регистрация: 13.03.2019 Сообщений: 23

	Нaйти местo из которого спичечная конструкция сгoрит зa нaименьшее врeмя 13.03.2019, 16:42. Показов 1104. Ответов 10 Метки нет (Все метки) Здравствуйте, формучане, вот такая головоломка мне попалась) Вообще не вдупляю что по чем, заранее благодарю за любую помощь На вхoд подаeтся числo - количeство спичeк. И для каждoй спички указываются кoординаты начaла спички, коoрдинаты кoнца спички и врeмя еe горeния. В полyчившейся кoнструкции нужнo нaйти такоe местo, в котороe eсли пyстить oгонь, oна сгoрит зa нaименьшее врeмя и соoтветственно вывeсти полyчившееся врeмя. Огoнь движeтся равнoмерно, eсли oн дoходит дo развeтвления, тo идет вo всe стoроны. Грyбo гoворя, вeдет сeбя как огoнь. Вoт тeст нa кoторoм будeт провeряться , там 16 спичeк, a в рeзультате дoлжно выйти 4.5 сeкунд 0

@MonstrTraf 0 / 1 / 0 Регистрация: 13.03.2019 Сообщений: 23
	13.03.2019, 18:28 [ТС]
	А может кто нибудь написать как это на С++ будет выглядеть? Я сути не понимаю... 0

@MonstrTraf 0 / 1 / 0 Регистрация: 13.03.2019 Сообщений: 23
	13.03.2019, 18:53 [ТС]
	Когда есть код я могу его прогнать по пунктам и в итоге догоню что к чему, так гораздо легче 0

@MonstrTraf 0 / 1 / 0 Регистрация: 13.03.2019 Сообщений: 23
	15.03.2019, 17:51 [ТС]
	UPP 0

@MonstrTraf 0 / 1 / 0 Регистрация: 13.03.2019 Сообщений: 23
	24.04.2019, 15:33 [ТС]
	А если в графе циклы, как перебирать все возможные варианты? 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	25.04.2019, 01:46
	MonstrTraf, попробуй применить алгоритм Флойда 0