трехмерное пространство, найти радиус Опции

[bairt]

В трехмерном пространстве задано N шаров. Найти шар минимального радиуса, охватывающий все заданные

[Бравый генерал]

lapp, а пост # 15 ты учел ?

klem4, ты так сказал, как будто после того поста решение КАРДИНАЛЬНО изменилось. Да, охватывающая сфера должна охватывать сферы, а не их центры, но сам костяк этого алгоритма неверен.

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

Во-во!

и для наглядности сначала делал с окружностями, типа в 2D

Вобщем, чтобы с тем неправильным алгоритмом было все ясно, вот эта программа - тот же алгоритм только в 2D, чтобы можно было проверить визуально. Бывают конечно случаи, когда охватывающая окружность охватывает ВСЕ окружности, но часто бывает, что сферы "вылазят" за охватывающую сферу, что и доказывает неправильность алгоритма.

Uses
 Crt, Graph;

Type
 Ball = record
	 x,y,r: Real
	end;

Const
 n = 10;

Var
 gd,gm: Integer;
 i,j,x,y,z: Byte;
 b: Array [1..n] of Ball;
 l,l0,d,dx,dy,x0,y0: Real;
 c: Ball;
 ch: char;

Function Ohvat(a,b: Ball): Real;
 var
  i: Byte;
 begin
  Ohvat:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))+a.r+b.r
 end; {Ohvat}

{****************************************************************************}

Begin
 Randomize;

 for i:=1 to n
 do begin
     b[i].x:=Random(400)+120;
     b[i].y:=Random(300)+90;
     b[i].r:=Random(50);
    end;

 InitGraph(gd,gm,'');

 l:=0;
 for i:=1 to n-1
 do for j:=i+1 to n
    do begin
	l0:=Ohvat(b[i],b[j]);
	 if l0 > l
	 then begin
	       l:=l0;
	       x:=i;
	       y:=j
	      end
       end;
 dx:=b[y].x-b[x].x;
 dy:=b[y].y-b[x].y;
 d:=sqrt(sqr(dx)+sqr(dy));
 c.r:=Ohvat(b[x],b[y])/2;
 c.x:=b[x].x + (c.r-b[x].r)*(dx/d);
 c.y:=b[x].y + (c.r-b[x].r)*(dy/d);

 for i:=1 to n
 do Circle(Round(b[i].x),Round(b[i].y),Round(b[i].r));
 setcolor(2);
 Circle(Round(c.x),Round(c.y),Round(c.r));

 ReadKey;

 CloseGraph
End.

Добавлено позже:

Бравый генерал, я сначала пропустил это, а сейчас перечитал и увидел: твое утверждение неверно. Вот опровергающий пример.

Да, прошу прощения, это я не то что-то сказал...
(Ой, надо было в предыдущий пост добавить, а я случайно новым отправил.)