Задача 102938
|
Название задачи: Путь на параллелепипеде . |
 |
Условие
На поверхности прямоугольного параллелепипеда { (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. Можно ли уменьшить указанное в алгоритме число перекатываний? На
сколько?
