Pagini recente » Cod sursa (job #1882829) | Cod sursa (job #2494372) | Cod sursa (job #2620871) | Cod sursa (job #2521289) | Cod sursa (job #363676)
Cod sursa(job #363676)
type punct=record
x,y:real;
end;
var p:array[0..120000] of punct;
s:array[1..120000] of punct;
polar:array[1..120000] of real;
n,varf,poz:longint;
xmin,ymin:real;
procedure citire;
var i:longint;
begin
assign(input,'infasuratoare.in'); reset(input);
readln(n);
for i:=1 to n do readln(p[i].x,p[i].y);
close(input);
end;
procedure varf_minim;
var i:longint;
begin
xmin:=maxlongint;
ymin:=maxlongint;
for i:=1 to n do
if p[i].x<xmin then
begin
ymin:=p[i].y;
xmin:=p[i].x;
poz:=i;
end
else if (p[i].x=xmin) and (p[i].y<ymin) then
begin
ymin:=p[i].y;
poz:=i;
end;
p[0].x:=xmin;
p[0].y:=ymin;
end;
procedure eliminare;
var i:longint;
begin
for i:=poz+1 to n do p[i-1]:=p[i];
dec(n);
end;
procedure formare;
var i:longint;
x,y,r:real;
begin
for i:=1 to n do
if p[i].x<>p[0].x then polar[i]:=arctan((p[i].y-p[0].y)/(p[i].x-p[0].x))
else polar[i]:=maxlongint;
end;
function dist(a,b:punct):real;
var x,y:real;
begin
x:=sqr(a.x-b.x);
y:=sqr(a.y-b.y);
dist:=sqrt(sqr(x)+sqr(y));
end;
procedure qsort(l,r:integer);
var i,j:longint;
aux1:punct;
v,aux:real;
begin
i:=l;
j:=r;
v:=polar[(l+r) div 2];
repeat
while polar[i]<v do inc(i);
while v<polar[j] do dec(j);
if i<=j then
begin
if polar[i]<>polar[j] then
begin
aux:=polar[i];
polar[i]:=polar[j];
polar[j]:=aux;
aux1:=p[i];
p[i]:=p[j];
p[j]:=aux1;
end
else if (polar[i]=polar[j]) and (dist(p[0],p[i])>dist(p[0],p[j])) then
begin
aux1:=p[i];
p[i]:=p[j];
p[j]:=aux1;
end;
inc(i);
dec(j);
end;
until i>=j;
if j>l then qsort(l,j);
if i<r then qsort(i,r);
end;
function produs_incrucisat(p1,p2,p3:punct):real;
begin
produs_incrucisat:=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
end;
procedure introducere(p1:punct);
begin
inc(varf);
s[varf]:=p1;
end;
procedure scanare_graham;
var i:integer;
prod:real;
begin
varf:=0;
introducere(p[0]);
introducere(p[1]);
for i:=2 to n do
begin
prod:=produs_incrucisat(s[varf-1],s[varf],p[i]);
if prod=0 then
begin
dec(varf);
introducere(p[i]);
end
else if prod>0 then introducere(p[i])
else begin
while (prod<=0) and (varf>1) do
begin
dec(varf);
prod:=produs_incrucisat(s[varf-1],s[varf],p[i]);
end;
introducere(p[i]);
end;
end;
end;
procedure afisare;
var i:longint;
begin
assign(output,'infasuratoare.out');rewrite(output);
writeln(varf);
for i:=1 to n do writeln(s[i].x:2:12,' ',s[i].y:2:12);
close(output);
end;
begin
citire;
varf_minim;
eliminare;
formare;
qsort(1,n);
scanare_graham;
afisare;
end.