Помогите с алгоритмом ..., ... поиск пути. Поделиться Опции

[ThinMoto]

Итак.

Имеется следующее задачко :

в точке (0;0) коорд. плоскости расположен источник света (лампочка ). Неподалеку от него находится выпуклый многоугольник с N вершинами (если верить преподу, многоугольник символизирует собой дом некоего Пети ). Сам Петя находится где-то в тени дома, известны его коорд. (х;у). Скорость передвижения Пети=v.

Итого :

необходимо найти минимальное время, за которое Петя может дотопать на свет, и написать программу, которая сможет его (время) вычислять.

Вроде все просто... Но блин никак не могу додуть, как рассчитать траекторию движения Пети, хоть убей. Помогите хоть советом, кто может... А то голова уже пухнет Код-то я накатать смогу, а воть как считать...

[Akceptor]

Кратчайший путь будет перпендикуляром к "тени".
1. Строим прямую по двум координатам (лампочка-угол "домика") - их будет аж 2
2. Строим перпендикуляр с точки "Петя" к этой прямой (тоже 2 штуки)
3. Вибираем меньший
_________________
Собственно, формулы для постороения уравнения прямой должны быть известны со школьной програмы, я их уже не помню.

Сообщение отредактировал Akceptor - 29.5.2008, 13:39

[mEASYn]

Сдуваю пыль со старых самодельных юнитов для паскаля )))

готовые функции пересечения прямых и отрезков вдруг пригодятся

Код

function twoline(x11,y11,x12,y12,x21,y21,x22,y22:single;var a,b:single):boolean;
         var s1,s2,x:single;
         begin
         if x12-x11=0 then x12:=x12+0.00001; if x22-x21=0 then x22:=x22+0.00001;
         s1:=(y12-y11)/(x12-x11); s2:=(y22-y21)/(x22-x21);
         if s1<>s2 then begin
         twoline:=true;
         a:=(x11*s1-x21*s2+y21-y11)/(s1-s2);
         b:=(a-x11)*s1+y11;
         end else twoline:=false;
         if x11>x12 then begin
         x:=x11; x11:=x12; x12:=x;
         end;
         if x21>x22 then begin
         x:=x21; x21:=x22; x22:=x;
         end;
         if (a<x11) or (a>x12) or (a<x21) or (a>x22) then twoline:=false;
         end;
function twopr(x11,y11,x12,y12,x21,y21,x22,y22:single;var a,b:single):boolean;
         var s1,s2,x:single;
         begin
         if x12-x11=0 then x12:=x12+0.00001; if x22-x21=0 then x22:=x22+0.00001;
         s1:=(y12-y11)/(x12-x11); s2:=(y22-y21)/(x22-x21);
         if s1<>s2 then begin
         twopr:=true;
         a:=(x11*s1-x21*s2+y21-y11)/(s1-s2);
         b:=(a-x11)*s1+y11;
         end else twopr:=false;
         end;

считаем, как говорилось ранее, две прямые. одна точка-лампочка, другие - два угла дома.
тангенс перпендикуляра от пети =1/(тангенс прямой от лампочки) , тангенсы это s1 и s2 в функциях...
находим их пересечение с перпендикуляром из пети (преобразуй формулу чтоб считало по одной точке и тангенсу).
ну а дальше ясно.

вроде не бред написал))