Pagini recente » Istoria paginii utilizator/raressarb | Istoria paginii utilizator/vladaturcan | Cod sursa (job #2457579) | Cod sursa (job #1184953) | Cod sursa (job #593129)
Cod sursa(job #593129)
const x:real=0.000000000001;
type punct=record x,y,z,d:real; end;
var a:array[1..120000] of punct;
n,i,j,p:longint;
minx,miny:real;
ok:boolean;
procedure Sort(l, r: Integer);
var
i,j: integer;
x:real;
y:punct;
begin
i := l; j := r; x := a[(l+r) DIV 2].z;
repeat
while a[i].z < x do i := i + 1;
while x < a[j].z do j := j - 1;
if i <= j then
begin
y := a[i]; a[i] := a[j]; a[j] := y;
i := i + 1; j := j - 1;
end;
until i > j;
if l < j then Sort(l, j);
if i < r then Sort(i, r);
end;
function verif(a,b,c:punct):boolean;
var ar:real;
begin
ar:=a.x*b.y+b.x*c.y+a.y*c.x-a.y*b.x-b.y*c.x-c.y*a.x;
if ar<-x then verif:=true else verif:=false;
end;
begin
assign(input,'infasuratoare.in');reset(input);
assign(output,'infasuratoare.out');rewrite(output);
readln(n);miny:=maxlongint;
for i:=1 to n do
begin
readln(a[i].x,a[i].y);
if (a[i].y-miny<-x) or ((abs(a[i].y-miny)<x) and (a[i].x-minx<-x)) then
begin
miny:=a[i].y;
minx:=a[i].x;
p:=i;
end;
end;
for i:=1 to n do
if i=p then a[i].z:=-3 else
begin
a[i].d:=sqrt(sqr(a[p].x-a[i].x)+sqr(a[p].y-a[i].y));
a[i].z:=(a[i].x-a[p].x)/a[i].d;
end;
sort(1,n);
i:=2;
while i<n do
begin
j:=i+1;
while abs(a[j].z-a[i].z)<x do
begin
if a[j].d>a[i].d then a[i]:=a[j];
a[j].z:=-2;
inc(j);
end;
i:=j;
end;
p:=3;
for i:=4 to n do
if a[i].z+2>x then
begin
ok:=verif(a[p-1],a[p],a[i]);
while not ok do
begin
dec(p);
ok:=verif(a[p-1],a[p],a[i]);
end;
inc(p);
a[p]:=a[i];
end;
writeln(p);
writeln(a[1].x:0:6,' ',a[1].y:0:6);
for i:=p downto 2 do writeln(a[i].x:0:6,' ',a[i].y:0:6);
end.