Помощь - Поиск - Пользователи - Календарь
Полная версия: построение выпуклой оболочки
Форум «Всё о Паскале» > Delphi, Assembler и другие языки. > Другие языки
Feagor
Паскалевский код
uses crt;
const armax=100;
var x,y,x1,y1:array[1..armax] of integer;
    i,j,n,k,gd,gm:integer;
    max_angle:real;
{------------------------------------------------------}
function ArcCos(arg:real):real;
var r:real;
  begin
  if (abs(arg)>1) then
    begin
    writeln(' Unavailable argument ');
    halt;
    end;
  if abs(arg)<0.000001
    then r := pi/2
    else r := ArcTan(sqrt(1/arg/arg-1));
  if arg<0 then r:=pi-r;
  ArcCos := r;
  end;
{------------------------------------------------------}

{------------------------------------------------------}
function angle(x1,y1,x2,y2,x3,y3:integer):real;
var l1,l2,l3,cosx:real;
begin
  l1:=sqrt(sqr(x2-x1)+sqr(y2-y1));
  l2:=sqrt(sqr(x3-x2)+sqr(y3-y2));
  l3:=sqrt(sqr(x3-x1)+sqr(y3-y1));
  cosx:=(l1*l1+l2*l2-l3*l3)/(2*l1*l2);
  angle:=arccos(cosx);
end;
{------------------------------------------------------}


begin
 clrscr;
 writeln('Kolichestvo tochek:');
 read(n);
 j:=2;
 max_angle:=0;
 for i:=1 to n do
    begin
      writeln('x[',i,']');
      read(x[i]);
      writeln('y[',i,']');
      read(y[i]);
    end;
 y1[1]:=y[1];
 x1[1]:=x[1];
  for i:=1 to n do
        begin
         if y[i]<y1[1] then begin y1[1]:=y[i]; x1[1]:=x[i]; end
         else if (y[i]=y1[1]) and (x[i]>x1[1]) then
                begin
                  y1[1]:=y[i]; x1[1]:=x[i];
                end;
        end;
  for i:=1 to n do
        begin
         if (x1[1]<>x[i]) and (y1[1]<>y[i]) then if (angle((x1[1]-3),y1[1],x1[1],y1[1],x[i],y[i])>max_angle) then
           begin
              max_angle:=angle((x1[1]-3),y1[1],x1[1],y1[1],x[i],y[i]);
              x1[2]:=x[i];
              y1[2]:=y[i];
           end;
        end;
  repeat
    inc(j);
    max_angle:=0;
    for i:=1 to n do
        begin
          if ((x1[j-2]=x[i]) and (y1[j-2]=y[i])) or
             ((x1[j-1]=x[i]) and (y1[j-1]=y[i])) then continue
          else
           begin
            if (angle(x1[j-2],y1[j-2],x1[j-1],y1[j-1],x[i],y[i])>max_angle) then
               begin
                 max_angle:=angle(x1[j-2],y1[j-2],x1[j-1],y1[j-1],x[i],y[i]);
                 x1[j]:=x[i];
                 y1[j]:=y[i];
               end;
           end;
        end;
  until (x1[j]=x1[1]) and (y1[j]=y1[1]);
  writeln('Obolochka idet cherez tochki:');
  for i:=1 to j-1 do writeln('x[',i,']=',x1[i],'   ','y[',i,']=',y1[i]);
  readkey;
end.
volvo
Программа с теми же тестами, на которых испытывалась Паскалевская версия - в аттаче:
Нажмите для просмотра прикрепленного файла

(раскомментируй потом ввод данных, и еще - это работает под ДОС-овским Turbo C, если у тебя другой компилятор - придется отказаться от использования clrscr())
Feagor
спасип=) +1
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.