Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Ада и другие языки _ построение выпуклой оболочки

Автор: Feagor 9.01.2008 12:52

Паскалевский код

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 9.01.2008 14:50

Программа с теми же тестами, на которых испытывалась Паскалевская версия - в аттаче:
Прикрепленный файл  0101.CPP ( 2.15 килобайт ) Кол-во скачиваний: 467


(раскомментируй потом ввод данных, и еще - это работает под ДОС-овским Turbo C, если у тебя другой компилятор - придется отказаться от использования clrscr())

Автор: Feagor 10.01.2008 15:47

спасип=) +1