Pagini recente » Cod sursa (job #1965972) | Cod sursa (job #520315) | Cod sursa (job #2397178) | Cod sursa (job #1220779) | Cod sursa (job #923990)
Cod sursa(job #923990)
program infasuratoare;
type hacking=record
x,y,dist,unghi:extended;
end;
const pi=3.14159265;
var f,g:text;
p:array[0..120000] of hacking;
min:longint;
i,n:longint;
bufin,bufout:array[1..65000] of byte;
st:array[1..120000] of hacking;
vf:longint;
determinant:extended;
vector:array[1..120000] of hacking;
procedure adauga_stiva (valoare:hacking);
begin
inc(vf);
st[vf]:=valoare;
end;
function calcul_determinant1(a,b,c:hacking):real;
begin
calcul_determinant1:=(a.x*b.y)+(a.y*c.y)+(b.x*c.y)-(c.x*b.y)-(a.x*c.y)-(b.x*a.y);
end;
procedure sterge_stiva;
begin
dec(vf);
end;
function pivot(st,dr:longint):longint;
var r,d,di:longint;
aux:hacking;
begin
r:=st;
d:=dr;
di:=1;
while r<d do
begin
if p[r].unghi>=p[d].unghi 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;
function calcul_determinant(p1,p2,p3:hacking):real;
begin
calcul_determinant:=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
end;
begin
assign (f,'infasuratoare.in'); reset (f);
assign (g,'infasuratoare.out'); rewrite (G);
settextbuf (f,bufin);
settextbuf (g,bufout);
readln (f,n);
min:=0;
p[0].y:=maxlongint; p[0].x:=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
begin
if i<>min then
begin
if p[i].x-p[min].x<>0 then
begin
p[i].unghi:=arctan ((p[i].y-p[min].y)/(p[i].x-p[min].x));
p[i].unghi:=p[i].unghi*(180/pi);
end
else
p[i].unghi:=90;
if p[i].unghi<0 then p[i].unghi:=180+p[i].unghi;
end;
end;
sort(1,n);
vf:=0;
adauga_stiva(p[1]);
adauga_stiva(p[2]);
for i:=3 to n do
begin
determinant:=calcul_determinant(st[vf-1],st[vf],p[i]);
if determinant=0 then
begin
sterge_stiva;
adauga_stiva(p[i]);
end
else
if determinant>0 then
begin
adauga_stiva(p[i]);
end
else
begin
while (determinant<=0) and (vf>1) do
begin
sterge_stiva;
determinant:=calcul_determinant(st[vf-1],st[vf],p[i]);
end;
adauga_stiva(p[i]);
end;
end;
writeln (g,vf);
for i:=1 to vf do
writeln (g,st[i].x:10:6,' ',st[i].y:0:6);
close (F); close (g);
end.