Pagini recente » Cod sursa (job #1443501) | Cod sursa (job #2244203) | Cod sursa (job #3249339) | Cod sursa (job #920423) | Cod sursa (job #1754086)
type Point=record
X,Y: real;
end;
var h, a:array[1..120000] of Point;
m, n:longint;
procedure init;
var i:longint;
begin
readln(n);
for i:=1 to n do readln(a[i].X, a[i].Y);
end;
procedure sw(var a,b:Point);
var c:Point;
begin
c:=a;
a:=b;
b:=c;
end;
procedure computeMin;
var i:longint;
begin
for i:=2 to n do
if (a[1].Y > a[i].Y) or (a[1].Y = a[i].Y) and (a[1].X > a[i].X)
then sw(a[1], a[i]);
end;
function det(p1,p2,p3: Point):real;
begin
det:=p1.X*p2.Y+p2.X*p3.Y+p3.X*p1.Y-p1.X*p3.Y-p2.X*p1.Y-p3.X*p2.Y;
end;
procedure qs(left, right: longint);
var i, j:longint; p:Point;
begin
i:=left; j:=right; p:=a[(i+j) div 2];
while i<j do
begin
while det(a[1], p, a[i])<0 do i:=i+1;
while det(a[1], p, a[j])>0 do j:=j-1;
if i<=j then begin
sw(a[i], a[j]);
i:=i+1;
j:=j-1;
end;
end;
if i<right then qs(i, right);
if j>left then qs(left, j);
end;
procedure hull;
var i:longint;
begin
m:=3;
for i:=1 to m do
h[i]:=a[i];
for i:=4 to n do
begin
m:=m+1;
h[m]:=a[i];
while (m>2) and (det(h[m-2], h[m-1], h[m]) <= 0) do
begin
h[m-1]:=h[m];
m:=m-1;
end;
end;
end;
procedure afisHull;
var i:longint;
begin
writeln(m);
for i:=1 to m do
writeln(h[i].X,' ', h[i].Y);
end;
begin
assign(input, 'infasuratoare.in');
reset(input);
assign(output, 'infasuratoare.out');
rewrite(output);
init;
computeMin;
qs(2, n);
hull;
afisHull;
end.