Задача 102942
|
Название задачи: Кратчайший путь в квадрате. |
 |
Условие
Внутрь квадрата с координатами левого нижнего угла (0, 0) и координатами правого верхнего угла (100, 100) поместили N квадратиков, стороны которых параллельны осям координат и имеют длину 5. Никакие два квадратика не имеют общих точек. Необходимо найти кратчайший путь из точки (0, 0) в точку (100, 100), который бы не пересекал ни одного из этих N квадратиков.Входные данные
В первой строке входного файла содержится целое число N (1 ≤ N ≤ 30), в каждой следующих N строк – координаты левого нижнего угла (x, y) очередного из квадратиков (0 ≤ x, y ≤ 95).
Выходные данные
Выведите в выходной файл координаты точек искомого пути, в которых меняется направление движения (включая начальную и конечную точки). Порядок точек в выходном файле должен соответствовать порядку точек в пути.
Пример входного файла
5
5 5
5 15
15 10
15 20
90 90
Пример выходного файла
0 0
5 10
20 20
95 90
100 100
Решение
Скачать архив тестов и решенийЛегко показать, что кратчайший путь может менять направление движения только в вершинах квадратиков (а также в начальной и конечной точках). Построим граф, вершины которого соответствуют всем указанным точкам. Если отрезок, соединяющий пару точек, не пересекает ни одного из квадратиков, то проведем между соответствующими вершинами графа ребро. Вес этого ребра положим равным длине рассматриваемого отрезка. Теперь осталось воспользоваться алгоритмом Дейкстры [Липский 88, п. 3.3] для нахождения кратчайшего пути между двумя вершинами полученного графа.
Упражнения
1. Действительно ли необходимо учитывать возможность прохождения пути через левые нижние и правые верхние углы квадратиков? Почему?
2. Покажите, как проверить пересечение отрезка с квадратиком, не используя чисел с плавающей точкой (для этого вполне достаточно типа Integer).
