Cod sursa(job #263316)
type t=record
x,y,u:real;
end;
var p,sol:array[0..30]of t;
f,g:text;
min:real;
i,n,m:integer;
function angle2(cx,cy:real):real;
var xcm,ycm,sinus,cosinus:real;
begin
xcm:=p[0].x;ycm:=p[0].y;
sinus:=(cy-ycm)/sqrt(sqr(cy-ycm)+sqr(cx-xcm));
cosinus:=(cx-xcm)/sqrt(sqr(cy-ycm)+sqr(cx-xcm));
if cosinus=0 then
begin
if sinus>0 then angle2:=pi/2 else if sinus<0 then angle2:=3*pi/2 end
else
begin
if (sinus>0) and (cosinus>0) then
angle2:=arctan(sinus/cosinus);
if (sinus>0) and (cosinus<0) then
angle2:=pi-arctan(abs(sinus/cosinus));
if (sinus<=0) and (cosinus<0) then
angle2:=pi+arctan(abs(sinus/cosinus));
if (sinus<=0) and (cosinus>0) then
angle2:=2*pi-arctan(abs(sinus/cosinus));
end;
end;
procedure citire;
begin
assign(f,'infasuratoare.in');reset(f);
readln(f,n);
readln(f,p[0].x,p[0].y);
for i:=1 to n-1 do
begin
readln(f,p[i].x,p[i].y);
p[i].u:=angle2(p[i].x,p[i].y);
end;
close(f);
end;
procedure minim;
var i:integer;
begin
min:=p[0].y;
for i:=1 to n-1 do
if p[i].y<min then
min:=p[i].y;
end;
procedure translatie;
var i:integer;
begin
for i:=1 to n-1 do
p[i].y:=p[i].y-min;
end;
procedure sortare;
var i:integer; sw:boolean; aux:t;
begin
sw:=true;
while sw=true do
begin
sw:=false;
for i:=1 to n-2 do
if p[i].u>p[i+1].u then
begin
aux:=p[i];
p[i]:=p[i+1];
p[i+1]:=aux;
sw:=true;
end;
end;
end;
function arie(x1,x2,x3,y1,y2,y3:real):real;
var x:real;
begin
x:=x1*y2+x2*y3+y1*x3-x3*y2-y3*x1-x2*y1;
arie:=x;
end;
procedure infasuratoare;
var i:integer;
begin
m:=1;sol[0]:=p[0];
for i:=1 to n-1 do
begin
if m=1 then
begin
sol[m]:=p[i];
m:=m+1;
end
else
begin
while (m>=2) and
(arie(p[i].x,sol[m-1].x,sol[m-2].x,p[i].y,sol[m-1].y,sol[m-2].y)>0) do
m:=m-1;
sol[m]:=p[i];
m:=m+1;
end;
end;
end;
procedure afisare;
var i:integer;
begin
assign(g,'infasuratoare.out');rewrite(g);
writeln(g,m);
for i:=0 to m-1 do
writeln(g,sol[i].x:6:6,' ',sol[i].y+min:6:6);
close(g);
end;
procedure retranslatare;
var i:integer;
begin
for i:=1 to m do
sol[i].y:=sol[i].y+min;
end;
begin
citire;
minim;
translatie;
sortare;
infasuratoare;
afisare;
end.