Pagini recente » Cod sursa (job #1821371) | Cod sursa (job #2738744) | Borderou de evaluare (job #367024) | Cod sursa (job #1535079) | Cod sursa (job #562933)
Cod sursa(job #562933)
program deyu;
const fi='infasuratoare.in';
fo='infasuratoare.out';
pi=3.14159265;
type rec=record
x,y,dist,up:extended;
end;
var f,g:text;
p:array[1..120000] of rec;
s:array[1..100000] of rec;
o:extended;
var n,i,j,min,vf:longint;
function pivot(st,dr:longint):longint;
var r,d,di:longint;
aux:rec;
begin
r:=st;
d:=dr;
di:=1;
while r<d do
begin
if p[r].up>=p[d].up then
begin
aux:=p[r];
p[r]:=p[d];
p[d]:=aux;
di:=-di;
end;
if di<0 then
dec(d) else
inc(r);
end;
pivot:=r;
end;
procedure sort(st,dr:longint);
var p1:longint;
begin
if st<dr then
begin
p1:=pivot(st,dr);
sort(st,p1-1);
sort(p1+1,dr);
end;
end;
procedure add(t:rec);
begin
inc(vf);
s[vf]:=t;
end;
procedure del;
begin
dec(vf);
end;
function produs(p1,p2,p3:rec):real;
begin
produs:=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
end;
begin
assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
read(f,n);
min:=0;
p[0].x:=maxlongint;
p[0].y:=maxlongint;
for i:=1 to n do
begin
read(f,p[i].x,p[i].y);
if p[i].y<p[min].y then
min:=i
else
if p[i].y=p[min].y then
if p[i].x<p[min].x then
min:=i;
end;
for i:=1 to n do
if i<>min then
begin
p[i].dist:=sqrt(sqr(p[i].x-p[min].x)+sqr(p[i].y-p[min].y));
if p[i].x-p[min].x<>0 then
begin
p[i].up:=arctan(((p[i].y-p[min].y)/(p[i].x-p[min].x)));
p[i].up:=p[i].up*(180/pi)
end
else
p[i].up:=90;
if p[i].up<0 then
p[i].up:=180+p[i].up;
end;
sort(1,n);
vf:=0;
add(p[1]);
add(p[2]);
for i:=3 to n do
begin
o:=produs(s[vf-1],s[vf],p[i]);
if o=0 then
begin
del;
add(p[i]);
end
else
if o>0 then
add(p[i])
else
begin
while (o<=0)and(vf>1) do
begin
del;
o:=produs(s[vf-1],s[vf],p[i]);
end;
add(p[i]);
end;
end;
writeln(g,vf);
for i:=1 to vf do
writeln(g,s[i].x:10:6,' ',s[i].y:10:6);
close(f);
close(g);
end.