При разводке печатной платы необходимо затратить как можно меньше места
и средств. Вам предлагается написать программу, которая частично решает эту
проблему.
Печатная плата представляется сеткой квадратных ячеек. Первоначально проведено несколько
дорожек, которые представляют собой цепочки последовательно соединенных ячеек.
Необходимо соединить дорожкой еще две точки подобным образом. Каждая клетка
дорожки (включая конечную и начальную) стоит одну единицу, однако, если
дорожка пересекает другую дорожку, то стоимость будет выше, а именно - k
(k>=2). В том случае, если дорожка пересекает место пересечения нескольких
дорожек, то стоимость проводки такой ячейки составляет соответственно n*k,
где n - количество уже пересекающихся в этом месте дорожек.
Необходимо провести дорожку таким образом, чтобы стоимость
проводки была минимальной. Гарантируется, что начальная и конечная точки
различны. Имя программы circuit.pas
Во входном файле circuit.dat первой строкой идет размер сетки 1
<size<100. Во второй строке - четыре координаты - точки, которые надо
соединить. В третьей строке - значение стоимости пересечения - k. Четвертая
содержит количество заданных заранее дорожек. Начиная с пятой, в каждой строке
задается дорожка в следующем формате: первое число - количество узловых (концевых
и поворотных) точек в дорожке. Далее пары чисел - последовательно координаты
узловых точек с начальной до конечной точки дорожек.
В выходном файле circuit.sol в первой строке содержится стоимость
проведения дорожки, во второй дорожка в таком же формате, как и во входных
данных. (Количество узловых точек и далее последовательно координаты узловых
точек)
