Построение выпуклой оболочки, нужна помощь...все совсем плохо=( Опции

[Feagor]

Условие:
даны действительные числа x1,y1,x2,y2,...xn,yn известно что точки p1,p2,...pn с коорданатами (x1,y1),(x2,y2),...(xn,yn) попарно различны. Найти выпуклый многоугольник с вершинами в некоторых из точек p1,p2,..pn, который содержит все точки p1,p2,...pn. Многоугольник должен быть предоставлен последовательностью вершин.
ваще хз как делать, листинг, то что понял как делать

uses crt;
const armax=100;
var x,y:array[1..armax] of integer;
    i,j,n:integer;
begin
clrscr;
 writeln('Kolichestvo tochek:');
 read(n);
 for i:=1 to n do
    begin
      writeln('x[',i,']');
      read(x[i]);
      writeln('y[',i,']');
      read(y[i]);
    end;
end.

Прошу помощи, завтра сдавать...

Сообщение отредактировано: Feagor - 24.12.2007 21:07

[Feagor]

такс....код немного увеличился по идее должен работать, но не работает....по идее работать должен через алгоритм Gift Wrapping. Прошу помощи.

uses crt;
const armax=100;
var x,y,x1,y1:array[1..armax] of integer;
    i,j,n,k:integer;
    min_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;
 min_angle:=4;
 for i:=1 to n do
    begin
      writeln('x[',i,']');
      read(x[i]);
      writeln('y[',i,']');
      read(y[i]);
    end;
  for i:=1 to n do
        begin
         if x[i]>x1[1] then x1[1]:=x[i];
         if y[i]>y1[1] then y1[1]:=y[i];
        end;
  for i:=1 to n do
        begin
         if (angle((x1[1]+3),y1[1],x1[1],y1[1],x[i],y[i])<min_angle) and (x1[1]<>x[i]) and (y1[1]<>y[i]) then
           begin
              min_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);
    min_angle:=4;
    for i:=1 to n do
        begin
          if (angle(x1[j-1],y1[j-1],x1[j],y1[j],x[i],y[i])<min_angle) and (x1[j]<>x[i]) and (y1[j]<>y[i]) then
               begin
                 min_angle:=angle(x1[j-1],y1[j-1],x1[j],y1[j],x[i],y[i]);
                 x1[j]:=x[i];
                 y1[j]:=y[i];
               end;
        end;
  until (x1[j]=x1[1]) and (y1[j]=y1[1]);
  readkey;
end.

Сообщение отредактировано: Feagor - 25.12.2007 11:44