Задано множество точек в трехмерном пространстве

[Ана99]

Задано множество точек в трехмерном пространстве

Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества.
Помогите пожалуйста! FreePascal или PascalABC.NET

 

[Vladimir_S]

Да... весёлая задачка. Завтра с утра поразмыслю - раньше, увы, не получится.

 

[Vladimir_S]

Получите:

Const
 Mmax=12; {Maximal number of points}

Type
 Coord=Record
        x,y,z:Integer;
       end;
 Ar=Array[1..Mmax] of Real;

Var
 M,N,i,j:Byte;
 Pnts:Array[1..Mmax] of Coord;
 Dist:Array[1..Mmax] of Ar;
 R:Ar;
 Rmin:Real;

Procedure Bubble(Q:Byte; var A:Ar);
var
 g,h:byte;
 D:real;
begin
 for g:=1 to Q-1 do
  for h:=1 to Q-g do
  if A[h]>A[h+1] then
   begin
    D:=A[h];
    A[h]:=A[h+1];
    A[h+1]:=D;
   end;
end;

Begin
 Randomize;

 M:=100;
 While M>Mmax do
  begin
   write('Global number of points = ');
   readln(M);
   if M>Mmax then writeln('Error: too many points!');
  end;

 N:=M+1;
 While N>=M do
  begin
   write('Number of points in sphere = ');
   readln(N);
   if N>=M then writeln('Error: too many points!');
  end;
 writeln;

 for i:=1 to M do
  begin
   Pnts[i].x:=-50+Random(101);
   Pnts[i].y:=-50+Random(101);
   Pnts[i].z:=-50+Random(101);
   writeln(i:3,'  x = ',Pnts[i].x:3,'  y = ',Pnts[i].y:3,'  z = ',Pnts[i].z:3);
  end;
 writeln('Press "Enter" to continue');
 readln;

 for i:=1 to M do
  for j:=1 to M do
   Dist[i][j]:=Sqrt(Sqr(Pnts[i].x-Pnts[j].x)+
                    Sqr(Pnts[i].y-Pnts[j].y)+
                    Sqr(Pnts[i].z-Pnts[j].z));

 for i:=1 to M do
  begin
   for j:=1 to M do write(Dist[i][j]:6:1);
   writeln;
  end;
 writeln('Press "Enter" to continue');
 readln;

 for i:=1 to M do Bubble(M,Dist[i]);

 for i:=1 to M do
  begin
   for j:=1 to M do write(Dist[i][j]:6:1);
   writeln;
  end;
 writeln('Press "Enter" to continue');
 readln;

 for i:=1 to M do R[i]:=Dist[i][N];

 Rmin:=200;

 for i:=1 to M do
  if R[i]<Rmin then Rmin:=R[i];

 writeln('Result: Rmin = ',Rmin:0:3);

 Readln
End.

Некоторые пояснения:
1. Задается общее количество точек в пространстве (M). Их максимальное количество ограничено двенадцатью просто для удобства вывода на экран.
2. Задается количество точек внутри шаров (N). Естественно, должно выполняться условие N<M.
3. С помощью генератора случайных чисел задаются координаты x, y, z каждой из точек. Координаты выводятся на экран.
4. Создается двумерный массив расстояний (Dist) от каждой из точек до всех остальных, включая саму точку. Результат выводится на экран.
5. Линейные массивы-строки упорядочиваются по возрастанию методом пузырька. Таким образом, имеем матрицу, каждая строка которой соответствует точке, а по столбцам - расстояния от этой точки до других точек в порядке возрастания расстояний. Результат выводится на экран.
6. Легко видеть, что число N - это ни что иное, как N-й номер столбца. Считываем этот столбец в массив R.
7. Находим в массиве R минимальный элемент.

Всё!!!