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

[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

[volvo]

просьба протестить

Потестил. Неправильный результат выдает на тестовых последовательностях:

const armax=8;
var
    x: array[1 .. armax] of integer = (
      3, 6, 6, 5, 7, 7, 4, 9
    );
    y: array[1 .. armax] of integer = (
      2, 1, 3, 4, 4, 6, 7, 7
    );

Чтобы поправить, пришлось сделать так:

repeat
  inc(j); { Заметь, ты увеличил 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

      {
       Я говорил, что ты увеличил J -
       поэтому теперь надо брать 2 последних найденных точки именно так
      }
      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]);

Вот теперь этот тест проходит... Надо еще на нескольких проверить, чтобы быть уверенным что это работает правильно... Тестируй дальше