|
Название задачи: Путь на параллелепипеде . |
 |
Условие
На поверхности прямоугольного параллелепипеда { (x, y, z) |
0 ≤ x ≤ L, 0 ≤ y ≤ W, 0 ≤ z ≤ H } отмечены две точки с координатами (x1, y1, z1) и
(x2, y2, z2). Существует много путей, проходящих по поверхности параллелепипеда и соединяющих заданные точки. Требуется найти квадрат длины
кратчайшего из таких путей.
Входные данные
Файл входных данных содержит (в указанном порядке) следующие 9 целых
чисел: L, W, H, x1, y1, z1, x2, y2, z2
. Числа разделяются пробелами и/или символами
перевода строки. Каждое из чисел L, W, H не превышает 100.
Выходные данные
Вывести в выходной файл одно целое число – квадрат длины искомого пути.
Пример входного файла
3 4 4
1 2 4
3 2 1
Пример выходного файла
25
Решение
Скачать архив тестов и решений
Пометим конечную точку краской. Пока краска не высохла, поставим
параллелепипед начальной точкой на начало координат плоскости Oxy. Теперь
будем перекатывать параллелепипед через его ребра всеми возможными
способами, выполняя не более 5 перекатываний от начального положения. В
результате конечная точка будет оставлять на плоскости Oxy отпечатки
(считаем, что на параллелепипеде отпечатков не остается).
Так как способов перекатывания много, то и следов конечной точки тоже
будет несколько. Минимальное из расстояний от начала координат плоскости
Oxy до отпечатка конечной точки и будет ответом задачи.
Упражнения
1. Докажите корректность приведенного алгоритма.
2. Можно ли уменьшить указанное в алгоритме число перекатываний? На
сколько?
