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

[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 - 25.12.2007 1:07

[Feagor]

2 volvo спасибо за помощь!!!! Все работает прекрасно единственно модно добавить условие, что при поиске следующей точки, если несколько углов имеют одинаковый угол, являющийся максимальным, брать ту до которой расстояние больше...ысчо раз спасибо, считаю что тема себя исчерпала, и её можно закрыть, рабочий код:

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.