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

[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

[Lapp]

Ответ Michael_Rybak'а является абсолютно полным и точным, но я боюсь, что он требует некоторого "разжевывания"..

1. Сделать функцию, возвращающую TRUE, если переданный ей отрезок НЕ имеет с квадратом общих точек. Заморачиваться с внутренностями (отсеивать касания границ) нет смысла, поскольку эти случаи так или иначе будут перечислены потом. Единственное, что важно - надо проверять на общие точки внутренность отрезка, а концы выпускать. Назовем такю функцию Clear(A,B), где А и В - точки, концы отрезка.

2. Если Clear(A,B) - все, задача решена. Ответ - отрезок АВ.

3. Min:=Len(А,В)*10; in:=0; jn:=0; (Len - это функция, возвращающая длину отрезка)

4. Цикл по всем вершинам квадрата (назову их Di, 1<=i<=4).
for i:=1 to 4 do if Clear(A,Di) and Clear(Di,B) and Len(A,Di)+Len(Di,B)<Min then in:=i;
(это не совсем паскалевский текст, индексы обозначены без скобок, дальше тоже так).

5. Если in>0 , то ответ - ломаная A-Din-B, выход.

6. Цикл по вершинам

for i:=1 to 4 do begin
  if Clear(A,Di) and Clear(Di+1,B) and Len(A,Di)+Len(Di+1,B)<Min then begin 
    in:=i;
    jn:=i+1
  end;
  if Clear(A,Di) and Clear(Di-1,B) and Len(A,Di)+Len(Di-1,B)<Min then begin 
    in:=i;
    jn:=i-1
  end
end;

7. Ответ - ломаная A-Din-Djn-B

Вот, примерно, так..