Pagini recente » Cod sursa (job #2089253) | Cod sursa (job #4174) | Cod sursa (job #1724159) | Cod sursa (job #2973544) | Cod sursa (job #926192)
Cod sursa(job #926192)
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;
procedure interclasare (st,dr,mijloc:longint);
var i,j,m,k:longint;
begin
i:=st; j:=dr+1;
m:=0;
while (i<=mijloc) and (j<=dr) do
begin
if p[i].unghi<p[j].unghi then
begin
inc(m); vector[m]:=p[i];
inc(i);
end
else
begin
inc(m); vector[m]:=p[j];
inc(j);
end;
end;
if i<=mijloc then
begin
for k:=i to mijloc do
begin
inc(m); vector[m]:=p[k];
end;
end;
if j<=dr then
begin
for k:=j to dr do
begin
inc(m); vector[m]:=p[k];
end;
end;
m:=0;
for i:=st to dr do
begin
inc(m); p[i]:=vector[m];
end;
end;
procedure sort(st,dr:longint);
var aux:hacking;
mijloc:longint;
begin
if dr-st<=1 then
begin
if p[st].unghi>=p[dr].unghi then
begin
aux:=p[st]; p[st]:=p[dr]; p[dr]:=aux;
end;
end
else
begin
mijloc:=(st+dr) div 2;
sort(st,mijloc);
sort(mijloc+1,dr);
interclasare (st,dr,mijloc);
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.