Pagini recente » Cod sursa (job #265177) | Cod sursa (job #1231553) | Cod sursa (job #1156344) | Cod sursa (job #650407) | Cod sursa (job #926209)
Cod sursa(job #926209)
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 sort (st,dr:longint);
var a,b,ma:longint;
aux:hacking;
begin
a:=st; b:=dr;
repeat
while p[a].unghi<p[b].unghi do dec(b);
aux:=p[a]; p[a]:=p[b]; p[b]:=aux;
inc(a);
ma:=1;
if a<b then
begin
while p[a].unghi<p[b].unghi do
inc(a);
aux:=p[a]; p[a]:=p[b]; p[b]:=aux;
dec(b);
ma:=0;
end;
until b<=a;
if st<a-ma then sort(st,a-ma);
if a-ma+1<dr then sort(a-ma+1,dr);
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.