нить, задача на расстояние Опции

[Bard]

ребята помогите пожалуйста с разработкой алгоритма и программы этой задачи:

На плоскости расположены квадрат и 2 точки. Указанные точки не могут находиться внутри квадрата, а лежат вне или на его границе. Между точками нужно натянуть нить. Нить не может проходить внутри квадрата, она может лишь соприкасаться с его границей. Нить достаточно тонкая, и ее толщиной можно пренебречь.
Квадрат задан координатами центра (Xc,Yc) и координатами одной из вершин (Xv,Yv). Точки заданы своими координатами (Xa,Ya) и (Xb,Yb). Все числа Xc, Yc, Xv, Yv, Xa, Ya, Xb, Yb являются целыми и не превосходят по модулю 10000. Стороны квадрата параллельны осям координат. На рисунке представлены два примера натяжения нити минимальной длины. Пунктиром показано неверное натяжение нити.
Найти наименьшую длину нити.

Например если вводиться
0 0 -1 -1 -1 -2 2 1
То надо вывести
4.47

у кого есть идеи???

Сообщение отредактировано: Bard - 23.05.2007 18:25

[Michael_Rybak]

Сначала покажи, что ответом всегда будет либо отрезок, соединяющий эти две точки (если он не пересекается с квадратом), либо путь вида первая_точка - вершина_квадрата - соседняя_с_ней_вершина - вторая точка.

Потом напиши процедуру, которая проверяет, имеет ли данный отрезок общие *внутренние* точки с квадратом.

Потом перебирай варианты. Что не ясно будет - спрашивай.