Версия для печати темы

Автор: artur89 4.09.2007 21:14

Вообщем дана лаба,в ней даны n окружностей и отрезков,выделить красным цветом ту окружность,которая пересекается с наибольшим количеством отрезков.
Вот,само задание 3 вариантов пересечений есть,я только не могу додуматься до конца как найти потом окружность с максимальным количеством пересечений.Была рабочая версия,но забраковал препод,мол не те формулы,пришлось вот делать через нормы векторов
Собственно сам участок кода :

function per(okr:T_okr;otr:T_otr):boolean;
var tmp1,tmp2,tmp3,tmp4,h,t:extended;
begin
     tmp3:=(okr.a-otr.x2)*(otr.x2-otr.x1)-(otr.y2-otr.y1)*(okr.b-otr.y2);
     tmp4:=(okr.a-otr.x1)*(otr.x1-otr.x2)-(otr.y1-otr.y2)*(okr.b-otr.y1);
     tmp1:=sqr((otr.x2-otr.x1)*(otr.x2-otr.x1)+(otr.y2-otr.y1)*(otr.y2-otr.y1));
     tmp2:=abs((okr.a-otr.x1)*(otr.y2-otr.y1)+(okr.b-otr.y1)*(otr.x1-otr.x2));
     t:=tmp2/tmp1;
     if tmp3<0 then
     begin
          h:=sqr((okr.a-otr.x2)*(okr.a-otr.x2)+(okr.b-otr.y2)*(okr.b-otr.y2));
     end
     else
     if tmp4<0 then
     begin
          h:=sqr((okr.a-otr.x1)*(okr.a-otr.x1)+(okr.b-otr.y1)*(okr.b-otr.y1));
     end
     else
     h:=t;
     per:=h<=sqr(okr.r);
end;

Где h это собственно факт пересечения
Как тут поступить?Далее по идее должна идти функция подсчета максимального количества пересечений,а далее уже проще,если ... то ... .
Спасибо

Автор: volvo 4.09.2007 21:25

Собственно, как ты реализуешь функцию определения, пересекается ли данная окружность с данным отрезком - это твое дело... Вопрос был в том, как посчитать, сколько раз каждая окружность пересекается со всеми отрезками? Вот так:

{
  для простоты считаю, что у тебя все окружности заданы в виде массива Okr,
  а все отрезки - в виде массива Otr (если у тебя по другому - расскажи, как)
}
...
max := 0; index := 0;
for i := 1 to n_okr do begin { n_okr - число окружностей }

  count := 0;
  for j := 1 to n_lines do begin { n_lines - число отрезков }
    if per(okr[i], otr[j]) then inc(count);
  end;

  if count  > max then begin
    max := count; index := i
  end;

end;
...

в результате у тебя в переменной index будет храниться номер окружности, пересекающейся