Pagini recente » Cod sursa (job #318890) | Cod sursa (job #1977232) | Cod sursa (job #2960485) | Cod sursa (job #848562) | Cod sursa (job #409971)
Cod sursa(job #409971)
const infile='infasuratoare.in';
outfile='infasuratoare.out';
maxn=120003;
var x,y:array[0..maxn]of real;
p,S:array[0..maxn]of longint;
n,vf,p0:longint;
procedure citire;
var i:longint;
begin
assign(input,infile); reset(input); readln(n);
p0:=1;
for i:=1 to n do begin
readln(x[i],y[i]);
if(y[i]<y[p0])or((y[i]=y[p0])and(x[i]<x[p0]))then p0:=i;
end;
close(input);
end;
procedure sort(st,dr:longint);
var i,j,a:longint;
xm,ym:real;
begin
i:=st; j:=dr; xm:=x[p[(i+j)div 2]]; ym:=y[p[(i+j)div 2]];
while(i<=j)do begin
while((x[p[j]]-x[p0])*(ym-y[p0]) < (xm-x[p0])*(y[p[j]]-y[p0]))do dec(j);
while((x[p[i]]-x[p0])*(ym-y[p0]) > (xm-x[p0])*(y[p[i]]-y[p0]))do inc(i);
if(i<=j)then begin
a:=p[i]; p[i]:=p[j]; p[j]:=a;
inc(i); dec(j);
end;
end;
if(i<dr)then sort(i,dr);
if(st<j)then sort(st,j);
end;
function det(p1,p2,p3:longint):real;
begin
det:=x[p1]*(y[p2]-y[p3])+x[p2]*(y[p3]-y[p1])+x[p3]*(y[p1]-y[p2]);
end;
procedure solve;
var i:longint;
begin
for i:=1 to n do if(i<>p0)then begin inc(p[0]); p[p[0]]:=i; end;
sort(1,p[0]);
vf:=3;
S[1]:=p0; S[2]:=p[1]; s[3]:=p[2];
for i:=3 to p[0] do begin
while(vf>2)and(det(S[vf-1],S[vf],p[i])<=0)do dec(vf);
inc(vf); S[vf]:=p[i];
end;
assign(output,outfile); rewrite(output);
writeln(vf);
for i:=1 to vf do writeln(x[S[i]]:16:6,' ',y[S[i]]:16:6);
close(output);
end;
begin
citire; solve;
end.