1. Квадрат

Треугольник задан на плоскости координатами своих вершин: (X₁,Y₁), (X₂,Y₂), (X₃,Y₃). Найти длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник так, чтобы все вершины треугольника находились внутри квадрата либо на его сторонах.

Задание Составьте программу SQUARE, которая по координатам вершин треугольника находит длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник. L достаточно найти с точностью 10^-4.

Входные данные Файл SQUARE.DAT содержит в одной строке действительные числа X₁ Y₁ X₂ Y₂ X₃ Y₃, разделенные пробелами, – координаты вершин треугольника (-10000 Ј X₁, Y₁, X₂, Y₂, X₃, Y₃ Ј 10000).

Пример входного файла

0.0 0.0 1.1 0.0 0.0 1.1

Выходные данные Файл SQUARE.SOL должен содержать одно число - длину L стороны искомого квадрата.

Пример выходного файла

1.1

2. Лабиринт

Лабиринт имеет форму квадрата, который состоит из Nґ N квадратных клеток, внутри которого вдоль сторон клеток могут быть расположены стены.

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

Задание Составьте программу MAZE, которая вычислит минимальное количество ходов, за которое путешественник может добраться до источника с координатами (P, Q), начав путь в клетке с координатами (1, 1).

Входные данные Входной текстовый файл MAZE.DAT в первой строке содержит числа N, K, P, Q (2Ј NЈ 200, 0Ј KЈ 250, 1Ј P,QЈ N). Следующие N-1 строк содержат по N целых чисел — признаков наличия горизонтальных стен между клетками. Следующие N строк содержат N-1 целых чисел — признаков наличия вертикальных стен между клетками. 0 означает отсутствие стены, 1 – присутствие.

Выходные данные Единственная строка выходного текстового файла MAZE.SOL должна содержать найденное минимальное количество ходов, или число –1, если путь найти не удалось

3

Дана символьная строка S длины N (0 Ј N Ј 100) и словарь, который содержит M слов (0 Ј M Ј 100), длина каждого из которых не превышает N. Строка и слова состоят из символов a, b, …, z.

Напишите программу CIPHER, которая определяет наименьшее количество символов, которое необходимо вычеркнуть из заданной строки S, чтобы результирующую строку можно было представить как последовательность слов словаря. Количество использований каждого слова не ограничивается. Считается, что пустую строку можно представить с помощью слов любого словаря.

Строка в примере после вычеркивания лишних букв f и t примет вид abachdsya (было сделано два вычеркивания: abafchtdsya), и может быть представлена как последвательность следующих слов: a, bach, dsy, a.

В первой строке входного файла CIPHER.DAT находится два целых числа N и M, оразделенных пробелом. Во второй строке находится символьная строка S. В каждой из следующих M строк находится слово словаря.

В единственной строке выходного файла CIPHER.SOL должно находиться натуральное число – минимальное количество вычеркиваний, после которых зашифрованная строка может быть представлена в виде последовательности слов словаря.

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

В первой строке входного файла SCHOOLS.DAT находятся два натуральных числа, разделенных пробелом: N (3 Ј N Ј 100), количество школ в городе, и M – количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: A_i, B_i, C_i, разделенных пробелами, где C_i – стоимость прокладки линии электроснабжения (1 Ј C_i Ј 300) от школы A_i до школы B_i (i=1,2,…,N).

В единственной строке выходного файла SCHOOLS.SOL должны содержаться два натуральных числа S₁ и S₂, разделенных пробелом – две наименьшие стоимости схем (S₁Ј S₂). S₁=S₂ тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.