Pagini recente » Cod sursa (job #749543) | Cod sursa (job #2671468) | Cod sursa (job #1070864) | Cod sursa (job #1713028) | Cod sursa (job #730031)
Cod sursa(job #730031)
Program convex_algoritm_graham;
type point=record
x,y : extended;
end;
var fi,fo : text;
i,n,k,k1,l,j,poz : longint; px,py:extended;
a:array[0..120000] of point;
p:array[0..120000] of extended;
t:array[0..120000] of longint;
Function sarrus(p1,p2,p3:point):extended;
begin
sarrus:=p1.x*p2.y+p2.x*p3.y+p3.x*p1.y
-p2.y*p3.x-p3.y*p1.x-p1.y*p2.x;
end;
Function polar(x,y:extended):extended;
begin
if x>0 then begin
if y>0 then polar:=arctan(y/x)
else polar:=arctan(y/x)+2*pi;
end
else if x<0 then polar:=arctan(y/x)+pi
else if x=0 then begin
if y>0 then polar:=pi/2
else if y<0 then polar:=3*pi/2
else polar:=0;
end;
end;
Procedure quick(left,right:longint);
var i,j:longint; r,q:extended;
t:point;
begin
r:=p[(left+right) div 2];
i:=left; j:=right;
while i<j do begin
while p[i]<r do i:=i+1;
while p[j]>r do j:=j-1;
if i<=j then begin
t:=a[i]; a[i]:=a[j]; a[j]:=t;
q:=p[i]; p[i]:=p[j]; p[j]:=q;
i:=i+1; j:=j-1;
end;
end;
if j>left then quick(left,j);
if i<right then quick(i,right);
end;
begin
assign(fi,'infasuratoare.in'); reset(fi); readln(fi,n); k1:=0;
assign(fo,'infasuratoare.out'); rewrite(fo);
for i:=1 to n do readln(fi,a[i].x,a[i].y);
px:=a[1].x; py:=a[1].y;
for i:=2 to n do
if a[i].y<py then begin px:=a[i].x; py:=a[i].y; end;
for i:=1 to n do p[i]:=polar(a[i].x-px,a[i].y-py);
quick(1,n); poz:=2; t[1]:=1; t[2]:=2;
for i:=3 to n do begin
if sarrus(a[t[poz-1]],a[t[poz]],a[i])>0 then begin
poz:=poz+1;
t[poz]:=i;
end
else begin
while sarrus(a[t[poz-1]],a[t[poz]],a[i])<0 do poz:=poz-1;
poz:=poz+1;
t[poz]:=i;
end;
end;
writeln(fo,poz);
for i:=1 to poz do writeln(fo,a[t[i]].x:0:6,' ',a[t[i]].y:0:6);
close(fi); close(fo);
end.