Напишсання програм SQUARE і MAZE (Завдання першого туру XIV Всеукраїнської олiмпiади з iнформатики)

XIV Всеукраїнська олімпіада з інформатики

Перший тур

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 – присутність.

Приклад вхідного файлу

3 1 2 3
0 0 0

0 1 0

1 0

1 0

0 0

Вихідні дані Єдиний рядок вихідного текстового файла MAZE.SOL має містити знайдену мінімальну кількість кроків, або число –1, якщо шлях знайти не вдалося.

Приклад вихідного файлу

3