@deadcandance

Достаточно распространенная олимпиадная задачка "Юный поджигатель". Может у кого завалялся код на C++?

Юный поджигатель
Имя входного файла: f.in.
Имя выходного файла: f.out.

На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки, а оси направлены вдоль линий сетки.
На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:
• Спички длины 1 выкладывались по сторонам клеток.
• Спички длины выкладывались по диагоналям клеток.
Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке, имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).
Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью). Спичка может гореть в нескольких местах (например, когда она загорается с двух концов; или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь распространяется по вновь подожженной спичке в обе стороны).
Напишите программу, которая определит, в какой точке нужно поджечь фигуру, чтобы она сгорела за минимальное время.
Формат входных данных
Во входном файле записано сначала число — количество спичек ( ). Затем идет пятерок чисел вида , задающих координаты концов спички и время ее сгорания при условии, что она будет подожжена с одного конца (гарантируется, что каждая спичка имеет длину 1 или , все спички образуют связную фигуру, и положение никаких двух спичек не совпадает). Все координаты — целые числа, по модулю не превышающие 200, время сгорания — натуральное число, не превышающее .
Формат выходных данных
Выведите координаты целочисленной точки, в которой нужно поджечь фигуру, чтобы она сгорела за наименьшее время, а затем время, за которое в этом случае фигура сгорит. Время должно быть выведено с точностью не менее 2-х знаков после десятичной точки. Если решений несколько, выведите любое из них.
Пример
f.in
3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50

f.out
2 2
35.00

Миниатюры

 

0

@CoderHuligan

0

MrGluck

Тема в разделе С. Вам С или С++?

0

@deadcandance

С++, недосмотрела

0

@Vvvllad

MrGluck, у Вас на C# кода нет случайно?

0

@TheCalligrapher

В условии задачи зияют какие-то недоговоренности... "Спички длины выкладывались"? Какой длины? "1 или "? 1 или что?

0

@Vvvllad

TheCalligrapher, да, и правда тут не всё написано. У меня есть полное задание документом

0

IGPIGP

Судя по рисунку - корень из двух. С точки зрения здравого смысла, это два разных вида спичек. С точки зрения математики - всё может происходить на сферической поверхности в вакууме. BTW, я никогда не пробовал поджечь сферу. Интересная задачка.

0

@Vvvllad

IGPIGP, да, одна спичка равна 1, а диагональная равна корень из двух

0

IGPIGP

Это значит что четырнадцать простых равны примерно десяти диагональным. В общем: -"In Double we trust!")

0

@Vvvllad

IGPIGP, вы могли бы могли помочь с написание кода?

0

IGPIGP

Прочитав задание полностью я понял что время сгорания задаётся для каждой спички. Это значит, что длина не имеет значения. Имеет значение лишь граф.
На форуме нет практики персонального выделения партнёра для общения свыше обыкновенной вежливости. Я думаю, каждый кому станет интересно, сможет попытаться.
От себя скажу лишь, что помощь в поднятии олимпийского веса, это не то чего стоит желать молодому, амбициозному штангисту. Выбирайте вес по плечу. Нет подвига в том, чтобы подойти к огромному снаряду с криком: -"Дядя, помоги!". Хотя некоторый коллективный подход возможен, конечно.
Как по мне, задаче непростая. Но я люблю лаконичные условия.

0