В теме одно сообщение

[Патрушева Анна]

№999 на informatics.mccme.ru
Задача : Юный поджигатель

На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.
На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:
• Спички длины 1 выкладывались по сторонам клеток.
• Спички длины выкладывались по диагоналям клеток.
Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке, имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).
Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью). Спичка может гореть в нескольких местах (например, когда она загорается с двух концов; или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь расползается по вновь подожженной спичке в обе стороны).
Напишите программу, которая определит, в какой точке нужно поджечь фигуру, чтобы она сгорела за минимальное время.
Формат входных данных
Во входном файле записано сначала число N — количество спичек (1N40). Затем идет N пятерок чисел вида X1, Y1, X2, Y2, T, задающих координаты концов спички и время ее сгорания при условии, что она будет подожжена с одного конца (гарантируется, что каждая спичка имеет длину 1 или , все спички образуют связную фигуру, и положение никаких двух спичек не совпадает). Все координаты — целые числа, по модулю не превышающие 200, время сгорания — натуральное число, не превышающее 107.
Формат выходных данных
Выведите координаты целочисленной точки, в которой нужно поджечь фигуру, чтобы она сгорела за наименьшее время, а затем время, за которое в этом случае фигура сгорит. Время должно быть выведено с точностью не менее 2-х знаков после десятичной точки. Если решений несколько, выведите любое из них.
Примеры

f.in
f.out
1
0 0 1 1 1
0 0
1.00
5
0 0 0 1 1
1 0 0 1 10
0 0 1 0 1
0 0 1 1 1
2 2 1 1 1
0 0
3.25
3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50
2 2
35.00
16
0 0 0 1 1 -2 –1 –3 –1 1 -2 –1 –1 0 1 -2 –1 –1 –2 1
-1 0 0 0 1 0 3 1 3 1 1 3 2 2 1 2 2 2 1 1
2 1 1 0 1 2 0 1 1 1 2 0 1 0 1 2 1 1 1 1
0 0 1 0 1 0 1 –1 1 1 -1 1 –1 2 1 0 3 –1 2 1
0 0
4.50
!Примечание
Частичные решения для случая, когда время сгорания каждой из спичек равно 1 (вне зависимости от ее длины), будут оцениваться приблизительно половиной баллов.
Решение
Прежде всего заметим, что спички могут пересекаться только концами, либо серединами. Других случаев пересечения быть не может. Таким образом, если разбить каждую спичку на две «половинки» вдвое меньшей длины, по полученные «полуспички» пересекаться будут только концами. Если все координаты исходных спичек умножить на два, то координаты всех «полуспичек» также будут выражаться целыми числами. Далее, если на два умножить также и время горения всех спичек, то время горения «полуспички» также будет выражаться целым числом секунд. Будем считать, что мы так уже поступили, и далее спичками именуются именно такие «полуспички».
Мы перешли к аналогичной задаче с вдвое большим количеством спичек с целыми координатами, пересекающихся только концами. Построим граф, ребрами которого будут спички, а вершинами – их концы. Задача сводится к нахождению такой вершины графа, при «поджигании» которой весь граф сгорает за минимальное время.
Будем решать задачу перебором по всем потенциальным «точкам поджигания». Так как в любом случае необходимо в выходной файл вывести кроме координат оптимальной точки общее время сгорания, задачу о нахождении времени сгорания графа при «поджигании» данной вершины тоже надо уметь решать.
Пусть нам дан граф, в котором на каждом ребре записано время сгорания соответствующей ему спички (эту величину будем называть весом или длиной ребра), и в нем зафиксирована некоторая вершина. Как найти время сгорания этого графа при «поджигании» этой вершины?
Ясно, что время сгорания графа равно расстоянию от зафиксированной вершины до наиболее удаленной от нее точки графа. Именно «наиболее удаленной точки», а не «наиболее удаленной вершины»! Простейший пример, где эти понятия различаются –треугольник.

Допустим, в приведенном выше примере времена горения вертикальной и диагональной спичек – одна секунда, а время горения горизонтальной спички – четыре секунды. Тогда при поджигании этой фигуры в верхней точке через секунду огонь достигнет обоих концов основания. Еще две секунды потребуется пламени, чтобы сжечь основание. Таким образом, хотя самая удаленная вершина находится на расстоянии 1 от точки поджигания, суммарное время сгорания такой фигуры равно трем секундам.
Вычислим кратчайшие расстояния от данной вершины до всех остальных. Кратчайшее расстояние соответствует моменту времени, когда огонь достигнет данной вершины. Для нахождения расстояний можно использовать, например, алгоритм Флойда.
Алгоритм Флойда находит кратчайшие расстояния между всеми парами вершин в графе, делая число операций, пропорциональное кубу числа вершин графа. Программа, реализующая алгоритм Флойда, выглядит следующим образом:

for k:=1 to N do
for i:=1 to N do
for j:=1 to N do
if a[i,j]<a[i,k]+a[k,j] then a[i,j]:=a[i,k]+a[k,j];

Остановимся на описании алгоритма Флойда более подробно. Пусть в матрице A[i,j] записаны длины ребер графа (элемент A[i,j] равен весу ребра, соединяющего вершины с номерами i и j, если же такого ребра нет, то в соответствующем элементе записано некоторое очень большое число, например, 109). Построим новые матрицы Ck[i,j] (k=0,…,N). Элемент матрицы Ck[i,j] будет равен минимальной возможной длине такого пути из i в j, что в качестве промежуточных вершин в этом пути используются вершины с номерами от 1 до k. То есть рассматриваются пути, которые могут проходить через вершины с номерами от 1 до k (а могут и не проходить через какие-то из этих вершин), но заведомо не проходят через вершины с номерами от k+1 до N. В матрицу записывается длина кратчайшего из таких путей. Если таких путей не существует, записывается то же большое число, которым обозначается отсутствие ребра.
Сформулируем следующие факты.
В матрице C0[i,j] записаны длины путей, которые не содержат ни одной промежуточной вершины. Таким образом, матрица C0[i,j] совпадает с исходной матрицей A[i,j].
В матрице CN[i,j] записаны минимальные длины путей, которые в качестве промежуточных вершин используют все вершины графа — то есть длины кратчайших путей, которые мы хотим получить.
Если у нас уже вычислена матрица Ck–1[i,j], то элементы матрицы Ck[i,j] можно вычислить по следующей формуле: Ck[i,j]:=min (Ck–1[i,j], Ck–1[i,k]+Ck–1[k,j]). В самом деле, рассмотрим кратчайший путь из вершины i в вершину j, который в качестве промежуточных вершин использует только вершины с номерами от 1 до k. Тогда возможно два случая:
Этот путь не проходит через вершину с номером k. Тогда его промежуточные вершины — это вершины с номерами от 1 до k–1. Но тогда длина этого пути уже вычислена в элементе Ck–1[i,j].
Этот путь проходит через вершину с номером k. Но тогда его можно разбить на две части: сначала мы из вершины i доходим оптимальным образом до вершины k, используя в качестве промежуточных вершины с номерами от 1 до k–1 (длина такого оптимального пути вычислена в Ck–1[i,k]), а потом от вершины k идем в вершину j опять же оптимальным способом, и опять же используя в качестве промежуточных вершин только вершины с номерами от 1 до k (Ck–1[k,j]).
Выбирая из этих двух вариантов минимальный, получаем Ck[i,j].
Последовательно вычисляя матрицы C0, C1, C2 и т.д. мы и получим искомую матрицу CN кратчайших расстояний между всеми парами вершин в графе.
Заметим теперь, что при вычислении очередной матрицы Ck нам нужны лишь элементы матрицы Ck–1, поэтому можно не хранить в памяти N таких матриц, а обойтись двумя — той, которую мы сейчас вычисляем, и той, которую мы вычислили на предыдущем шаге. На самом деле оказывается, что даже это излишне — все вычисления можно производить в одной матрице (подумайте, почему).
Вернемся к решению нашей задачи.
После нахождения кратчайших путей из «поджигаемой» вершины во все остальные, нам известно время, за которое огонь достигнет каждой из вершин. Теперь нужно проверить все ребра-спички на предмет того, сгорели ли они уже в процессе перемещения огня до вершин, а если нет, то нужно найти время, когда догорит данное ребро. Максимальное из этих времен даст ответ.
Пусть огонь достигает концов спички со временем сгорания L в моменты времени T1 и T2. Если T1 = T2+L или T2 = T1+L, то огонь передавался по этой спичке, и максимум из T1 и T2 и будет тем временем, к которому спичка сгорит полностью. Отметим, что разность между T1 и T2 не может быть больше L (подумайте, почему).
Пусть теперь разность между T1 и T2 не равна L. Это значит, что к разным концам спички огонь подошел разными путями, она будет гореть одновременно с обеих сторон и догорит где-то посередине. Напомним, что под спичкой мы понимаем половину спички, и пересекаться не в концах она уже ни с чем не может. То есть поджечь такая спичка никакую другую спичку не может – с обеих ее концов уже и так бушует пламя! В простейшем случае, если спичка подожжена одновременно с обоих концов, она сгорает за время L/2. Трудность в том, что в общем случае время возгорания концов спички может не совпадать.
Можно вычесть одно и то же число из T1 и из T2, т.е. мы можем перейти к задаче, где один конец загорается во момент времени 0, а второй – в момент времени T. Общее время сгорания спички в таком случае будет равно T + (L-T)/2. Прийти к этой формуле проще всего из следующих соображений. Пусть спичка имеет длину L сантиметров и горит со скоростью 1 сантиметр в секунду. Тогда первые T секунд она будет гореть с одного конца, и сгорит на T см., а оставшееся время потребуется на то, чтобы сжечь L-T см со скоростью 2 см/сек, т.е. время сгорания этого куска спички будет равно (L-T)/2. При T = 0 формула дает ответ L/2, а при T = L - ответ L, что полностью согласуется с условием задачи.
Мы полностью умеем решать задачу о нахождении времени сгорания данной фигуры из спичек при ее поджигании в данной точке. Для этого нужно в соответствующем данной фигуре графе найти максимум из времен «догораний» каждого из ребер. И не забыть разделить его пополам – ведь при построении графа мы удвоили время сгорания каждой из спичек.
Теперь мы легко можем решить задачу перебором по вершинам. Проверив все потенциальные точки поджога и выбрав из них ту, при поджоге которой время сгорания минимально, мы найдем ответ. Необходимо учесть, что не каждая из вершин достроенного графа может быть точкой «поджигания». Так как мы раздвоили каждую спичку, в наш граф войдут также вершины, соответствующие серединам спичек. Из всех точек мы должны выбрать те, координаты которых нацело делятся на 2.
Еще одно замечание – в данной задаче мы всюду работали с целыми числами. Но в двух местах это целое число делилось на два – при нахождении координат пересечения спичек и при вычислении времени сгорания спички, подожженной с обеих сторон. Из этого следует, что общее время сгорания можно представить в виде X/4, где X – целое число. Соответственно, дробная часть этого времени будет равна 0.0, 0.25, 0.5 или 0.75, и двух десятичных знаков для ее представления вполне достаточно.

Приведем полный текст программы:
Program Matches;

Const
TaskID='f';
InFile=TaskID+'.in';
OutFile=TaskID+'.out';

Const
MaxN=42; { Ограничение на N }
MaxG=2*MaxN+1; { Ограничение на число вершин в графе }
Infinity=MaxLongInt; { "Бесконечное" расстояние }

Var
N:Integer; { }
Match:Array[1..MaxN]Of Record { Входные }
X1,Y1,X2,Y2:Integer; { данные }
Time:LongInt; { }
End; { }

NG:Integer; { }
Vertex:Array[1..MaxG]Of Record { }
X,Y:Integer; { Граф }
End; { }
Edge,Distance:Array[1..MaxG,1..MaxG]Of LongInt; { }

Res:Extended; { Минимальное время сгорания }
ResX,ResY:Integer; { Оптимальная точка поджога }

Procedure Load;
Var
I:Integer;
Begin
Assign(Input,InFile);
ReSet(Input);
Read(N);
For I:=1 To N Do
With Match[I] Do
Read(X1,Y1,X2,Y2,Time);
Close(Input);
End;



Function GetVertex(VX,VY:Integer):Integer;
{ Функция, возвращающая номер вершины с заданными координатами.
При отсутствии нужной вершины она создаётся }
Var
I:Integer;
Begin
For I:=1 To NG Do
With Vertex[I] Do
If (X=VX) And (Y=VY) Then Begin
GetVertex:=I;
Exit;
End;

Inc(NG); { Если нужная вершина не найдена }
With Vertex[NG] Do Begin
X:=VX;
Y:=VY;
For I:=1 To NG-1 Do Begin
Edge[I,NG]:=Infinity;
Edge[NG,I]:=Infinity;
End;
Edge[NG,NG]:=0;
End;
GetVertex:=NG;
End;

Procedure AddEdge(X1,Y1,X2,Y2:Integer; Time:Longint);
{ Функция, добавляющая ребро между двумя точками }
Var
A,B:Integer;
Begin
A:=GetVertex(X1,Y1);
B:=GetVertex(X2,Y2);
Edge[A,B]:=Time;
Edge[B,A]:=Time;
End;

Procedure BuildGraph; { Процедура построения графа }
Var
I:Integer;
Begin
NG:=0;
For I:=1 To N Do
With Match[I] Do Begin
AddEdge(X1*2,Y1*2,X1+X2,Y1+Y2,Time);
AddEdge(X1+X2,Y1+Y2,X2*2,Y2*2,Time);
End;
End;

Procedure FindShortestPaths;
Var
K,I,J:Integer;
Begin
Distance:=Edge;
For K:=1 To NG Do
For I:=1 To NG Do If Distance[I,K]<Infinity Then
For J:=1 To NG Do If Distance[K,J]<Infinity Then
If Distance[I,K]+Distance[K,J]<Distance[I,J] Then
Distance[I,J]:=Distance[I,K]+Distance[K,J];
End;



Function BurnAt(At:Integer):Extended;
{ Функция, вычисляющая время сгорания при поджоге в точке At }
Var
I,J:Integer;
Cur,ThisEdge:Extended;
Begin
Cur:=0;
For I:=1 To NG Do If Distance[At,I]>Cur Then Cur:=Distance[At,I];
For I:=1 To NG Do
For J:=I+1 To NG Do If Edge[I,J]<Infinity Then Begin
If (Distance[At,I]<Distance[At,J]+Edge[I,J]) And
(Distance[At,J]<Distance[At,I]+Edge[I,J]) Then Begin
If Distance[At,I]<Distance[At,J] Then
ThisEdge:=Distance[At,J]+(Edge[I,J]-(Distance[At,J]-Distance[At,I]))/2
Else
ThisEdge:=Distance[At,I]+(Edge[I,J]-(Distance[At,I]-Distance[At,J]))/2;
If ThisEdge>Cur Then Cur:=ThisEdge;
End;
End;
BurnAt:=Cur;
End;

Procedure Solve;
Var
I:Integer;
Cur:Extended;
Begin
Res:=Infinity;
For I:=1 To NG Do
With Vertex[I] Do
If Not Odd(X) And Not Odd(Y) Then Begin
Cur:=BurnAt(I);
If Cur<Res Then Begin
Res:=Cur;
ResX:=X Div 2;
ResY:=Y Div 2;
End;
End;
End;

Procedure Save;
Begin
Assign(Output,OutFile);
ReWrite(Output);
WriteLn(ResX,' ',ResY);
WriteLn(Res/2:0:2);
Close(Output);
End;

Begin
Load;
BuildGraph;
FindShortestPaths;
Solve;
Save;
End.

[neMakse4ka]

Интересная задача, и разбор понятный!