Радиус и центр окружности. - Pascal

Узнай цену своей работы

Формулировка задачи:

Задача: Определите радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек на плоскости и содержащей внутри наибольшее количество точек этого множества. Есть идея решения, но опыта и навыков работы в Паскале не хватает для реализации программы. Точки можно ввести любым способом хоть с клавиатуры, хоть рандомно. Для начала нужно найти центр круга, это делается по очереди перебирая все точки на плоскости!!! Например взяли первую точку, дальше нужно посчитать длину от той точки которую мы взяли до всех остальных по очереди!!!Если найдем >=3 отрезка одинаковой длины(это относительно одинаковой так как малая вероятность что длинна отрезков будет идентично равна, лучше значения округлить) Если нашли одну окружность это еще не означает что не может быть другой окружности, но задание стоит таким образом что нужно найти окружность которая содержит в себе наибольшее количество точек множества!!!

Решение задачи: «Радиус и центр окружности.»

textual
Листинг программы
program Triangle;
 
TYPE
  Points=array[1..2] of real;
  mat3=array[1..3,1..3] of real;
  mat4=array[1..4,1..4] of real;
var
    p:array[1..30] of points;
    i,j,k,l,{счетчики}
    n,{количество точек}
    vnutri,vne, {количество точек внутри и вне окружности}
    vnutriTemp, vneTemp {количество точек внутри и вне окружности, временные переменные}
   :integer;
    matr3:mat3;{квадратная матрица 3-го порядка}
    matr4:mat4; {квадратная матрица 4-го порядка}
    x0,y0,{центр окружности}
    a,b,c,{стороны треугольника}
    r,square,{радиус и площадь}
    det,{определитель}
    pol,{полупериметр}
    pk{подкоренное ввыражение, формуле герона}
    :real;
 
 
    {функция нахождения длины между точками}
    function dlina(p1,p2:points):real;
      begin
        dlina:=sqrt(sqr(p1[1]-p2[1])+sqr(p1[2]-p2[2]));
      end;
 
    {функция нахождения определителя 3-го порядка}
    function determine3(A:mat3):real;
      begin
      determine3:=a[1,1]*a[2,2]*a[3,3]+a[2,1]*a[3,2]*a[1,3]+
        a[3,1]*a[1,2]*a[2,3]-a[3,1]*a[2,2]*a[1,3]-a[2,1]*a[1,2]*a[3,3]-
        a[1,1]*a[3,2]*a[2,3];
      end;
 
 
   procedure GetMatr(a:mat4; var b:mat3; m:integer);
    { Вычеркивание из матрицы m-го столбца и первой строки, процедура нужнаая
    при нахождении определителя 4-го порядка }
    var
      i,j:integer;
    begin
      for i:=2 to 4 do
        for j:= 1 to 4 do
          begin
            if j=m
              then
                  continue
              else
                if j<m
                  then
                    b[i-1,j]:=a[i,j]
                  else
                    b[i-1,j-1]:=a[i,j];
          end;
    end;
 
    {определитель 4-го порядка}
    function determine4(A:mat4):real;
      var
        i,st:integer;
        tA:mat3;
        S:real;
      begin
        st:=1;
        s:=0;
        for i:= 1 to 4 do
          begin
            GetMatr(a,tA,i);
            s:=s+st*determine3(tA)*a[1,i];
            st:=st*(-1);
          end;
        determine4:=s;
      end;
 
 
 
begin
  { TODO -oUser -cConsole Main : Insert code here }
  {количество точек}
  writeln('Введите количество точек');
  readln(N);
 
  {ввод координат}
  for i:= 1 to N do
    begin
      writeln('Введите координаты  ',i,'-й вершины (x,y)');
      readln(p[i,1],p[i,2]);
    end;
 
    {инициализация переменных, точнее просто заполнение нулями}
    vnutri:=0;
    vne:=N;
    vnutriTemp:=0;
    vneTemp:=0;
    x0:=0;
    r:=0;
    y0:=0;
    square:=0;
    {перебор всех точек}
    for i:= 1 to N do
      for j:= 1 to N do
        for k:= 1 to N do
          {условие чтоб точки не совпадали}
          if (i<>j) and (i<>k) and (j<>k) then
            begin
             {нахождение площади и радиуса}
             a:=dlina(p[i],p[j]);
             b:=dlina(p[k],p[j]);
             c:=dlina(p[k],p[i]);
             pol:=(a+b+c)/2;
             pk:=pol*(pol-a)*(pol-b)*(pol-c);
             if pk<=0 then continue else square:=sqrt(pk);
             r:=(a*b*c)/(4*square);{радиус окружности}
              {цикл для перебора всех точек кроме точек треугольника}
              for l:= 1 to N do
                {четвертая точка чтоб не совпадала с точками треугольника}
                if  (l<>i) and (l<>j) and (l<>k)  then
                 begin
                 {заполнение матрицы}
                  matr4[1,1]:=sqr(p[l,1])+sqr(p[l,2]); matr4[1,2]:=p[l,1]; matr4[1,3]:=p[l,2]; matr4[1,4]:=1;
                  matr4[2,1]:=sqr(p[i,1])+sqr(p[i,2]); matr4[2,2]:=p[i,1]; matr4[2,3]:=p[i,2]; matr4[2,4]:=1;
                  matr4[3,1]:=sqr(p[j,1])+sqr(p[j,2]); matr4[3,2]:=p[j,1]; matr4[3,3]:=p[j,2]; matr4[3,4]:=1;
                  matr4[4,1]:=sqr(p[k,1])+sqr(p[k,2]); matr4[4,2]:=p[k,1]; matr4[4,3]:=p[k,2]; matr4[4,4]:=1;
                  det:=determine4(matr4);
                  {находим определитель и сравниваем знак}
                  if det>0 then inc(vneTemp) else inc(vnutriTemp);
                 end;
             {если при вершинах треугольника i,j,k разность точек минимальна
             то находим центр окрцжности }
             if abs(vne-vnutri)>abs(vneTemp-vnutriTemp)
                  then
                    begin
                      {нахождение центра окружности}
                      matr3[1,1]:=sqr(p[i,1])+sqr(p[i,2]); matr3[1,2]:=p[i,2]; matr3[1,3]:=1;
                      matr3[2,1]:=sqr(p[j,1])+sqr(p[j,2]); matr3[2,2]:=p[j,2]; matr3[2,3]:=1;
                      matr3[3,1]:=sqr(p[k,1])+sqr(p[k,2]); matr3[3,2]:=p[k,2]; matr3[3,3]:=1;
                      x0:=determine3(matr3)/(4*square);
                      matr3[1,2]:=p[i,1]; matr3[2,2]:=p[j,1]; matr3[3,2]:=p[k,1];
                      y0:=(-1)*(determine3(matr3))/(4*square);
                      vnutri:=vnutriTemp;
                      vne:=vneTemp;
                    end;
                vnutriTemp:=0;
                vneTemp:=0;
                end;
      {вывод данных}
      writeln('x0=',x0:5:3);
      writeln('y0=',y0:5:3);
      writeln('r=',r:5:3);
     readln;
end.

Объяснение кода листинга программы

Этот код написан на языке Pascal и предназначен для нахождения центра окружности и её радиуса на основе координат n точек. В начале кода определены типы данных и переменные, используемые в программе. Затем идет цикл, в котором пользователь вводит количество точек (n), а затем вводятся координаты каждой точки. Далее идет проверка на пересечение точек, которые составляют треугольник. Если точки не пересекаются, то находится центр окружности и радиус, вычисляется площадь окружности и сравнивается с площадью окружности, образованной пересечением трех точек. Если площади равны, то центр окружности находится внутри треугольника, иначе - вне его. Затем находится определитель 4-го порядка и сравнивается с нулем. Если он положительный, то центр окружности находится внутри треугольника, если отрицательный - вне треугольника. В конце кода выводятся координаты центра окружности (x0, y0) и радиус r.

Оцени полезность:

6   голосов , оценка 4.5 из 5
Похожие ответы