Pagini recente » Cod sursa (job #677048) | Cod sursa (job #2742816) | Cod sursa (job #694379) | Cod sursa (job #15175) | Cod sursa (job #283735)
Cod sursa(job #283735)
var n,m,i,j,nst, p1, p2,c1,c2:integer;
mx,my:real;
x,y: array[1..120000] of real;
f: text;
st: array [1..120000] of integer;
procedure Sort(l, r: Integer);
var
i, j, a: integer;
yy: real;
begin
i := l; j := r; a := (l+r) DIV 2;
repeat
while y[i]*x[a] < y[a]*x[i] do i := i + 1;
while y[a]*x[j] < y[j]*x[a] do j := j - 1;
if i <= j then
begin
yy := x[i]; x[i] := x[j]; x[j] := yy;
yy := y[i]; y[i] := y[j]; y[j] := yy;
i := i + 1; j := j - 1;
end;
until i > j;
if l < j then Sort(l, j);
if i < r then Sort(i, r);
end;
function dist (p1,p2 : integer): real;
begin
dist:= sqr(x[p1]-x[p2]) + sqr(y[p1]-y[p1]);
end;
begin
assign (f,'infasuratoarea.in');
reset (f);
readln (f,n);
mx := 2000000000;
my := 2000000000;
for i:=1 to n do
begin
readln (f, x[i], y[i]);
if y[i]<my then
begin
my:= y[i];
mx:= x[i];
end
else
if (my=y[i]) and (x[i]<mx) then
mx := x[i];
end;
for i:=1 to n do
begin
y[i] := y[i] - my;
x[i] := x[i] - mx;
end;
close (f);
Sort(2,n);
nst:=2;
st[1]:=1;
st[2]:=2;
for i:=3 to n do
begin
while (nst>1) and ((x[st[nst]]-x[st[nst-1]])*(y[i]-y[st[nst-1]]) + (x[i]-x[nst-1])*(y[st[nst-1]]-y[st[nst]]) < 0 )do
dec(nst);
inc(nst);
st[nst]:=i;
end;
assign(f,'infasuratoarea.out');
rewrite(f);
writeln(f,nst);
for i:=1 to nst do
writeln(f,x[st[i]]+mx:0:6,' ',y[st[i]]+my:0:6);
close(f);
{
p1:=1; p2:=1;
while (p2<nst) and (dist(st[p1],st[p2]) < dist(st[p1],st[p2+1])) do inc(p2);
c1:=p1; c2:=p2;
while (p2<nst) do
begin
inc(p1);
while (p2<nst) and (dist(st[p1],st[p2]) < dist(st[p1],st[p2+1])) do
begin
inc(p2);
if dist(st[c1],st[c2])< dist(st[p1],st[p2]) then
begin
c1:=p1;
c2:=p2;
end;
end;
end;
}
end.