Задача на построение ломаной

[RedMonk]

Здравствуйте!

Есть следующая задача. На плоскости есть точки A и B, а также набор прямоугольников, ребра которых параллельны осям координат. Точки A и B не принадлежат прямоугольникам. Необходимо создать алгоритм, который ломаную, соединяющую A и B, такую, что:
1) ломаная состоит только из отрезков, которые параллельны осям координат
2) ломаная не пересекает ни один прямоугольник
3) у ломаной минимальное количество изломов
4) у ломаной минимальная длина

Подскажите, пожалуйста, источники, которые могут помочь решить задачу.

Спасибо!

[warlock66613]

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

-- 19.07.2014, 14:57 --

warlock66613 в сообщении #888706 писал(а):

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

[glukmaker]

RedMonk в сообщении #888656 писал(а):

Здравствуйте!

Есть следующая задача. На плоскости есть точки A и B, а также набор прямоугольников, ребра которых параллельны осям координат. Точки A и B не принадлежат прямоугольникам. Необходимо создать алгоритм, который ломаную, соединяющую A и B, такую, что:
1) ломаная состоит только из отрезков, которые параллельны осям координат
2) ломаная не пересекает ни один прямоугольник
3) у ломаной минимальное количество изломов
4) у ломаной минимальная длина

Подскажите, пожалуйста, источники, которые могут помочь решить задачу.

Спасибо!

Хм. Ну я понимаю все кроме последнего пункта, насчет минимальной длины.

Например есть у нас точки A(1,5) , B(10,5) и прямоугольник (2,7)-(9,0)

Очевидно что ломаная будет такой (1,5)-(1,7+dy)-(10,7+dy) - (10,5)
где dy ненулевая, но бесконечно малая величина. Как Вы собираетесь ее представлять ?