Pagini recente » Cod sursa (job #2605939) | Cod sursa (job #913851) | Cod sursa (job #1427126) | Cod sursa (job #1501706) | Cod sursa (job #724517)
Cod sursa(job #724517)
program infasuratoare;
type pct=record x,y:real; end;
var fi,fo:Text;
bufin,bufout:array[1..1 shl 17]of char;
p:array[1..120000]of pct;
m,pas,i,n,k:longint;
st:Array[1..120000]of longint;
procedure pivot(s,d:longint);
var a,b,ai,bi:longint;
aux:pct;
begin
a:=s; b:=d; ai:=0; bi:=1;
while a<b do
begin
if (p[a].y>p[b].y) or ((p[a].y=p[b].y) and (p[a].x>p[b].x)) then
begin
aux:=p[a]; p[a]:=p[b]; p[b]:=aux;
a:=ai; ai:=bi; bi:=a;
end;
a:=a+ai; b:=b-bi;
end;
m:=a;
end;
procedure quick(s,d:longint);
begin
if s<d then
begin
pivot(s,d);
quick(s,m-1);
quick(m+1,d);
end;
end;
procedure modifica;
begin
if pas=1 then
begin
inc(i);
if i=n then pas:=-1;
end
else dec(i);
end;
function semn(a,b,c:pct):integer;
begin
//calculez determinantul
if (A.y-b.y)*c.x+(b.x-a.x)*c.y+a.x*b.y-a.y*b.x <=0 then semn:=-1
else semn:=1;
end;
procedure infasuratoare;
var v:array[1..120000]of boolean;
punct1,punct2,punct3:pct;
begin
for i:=1 to n do v[i]:=false;
pas:=1;
st[1]:=1; st[2]:=2; v[2]:=true; //am selectat punctul 2
k:=2; i:=2;
while i>1 do
begin
while v[i] do modifica;
if i=0 then break;
while (k>1) and (semn(p[st[k-1]],p[st[k]],p[i])>0) do
begin
v[st[k]]:=false;
dec(k);
end;
inc(k);
st[k]:=i;
v[i]:=true;
end;
end;
begin
assign(fi,'infasuratoare.in'); reset(fi); settextbuf(fi,bufin);
assign(fo,'infasuratoare.out'); rewrite(fo); settextbuf(fo,bufout);
readln(fi,n); //numarul de puncte din plan
for i:=1 to n do read(fi,p[i].x, p[i].y); //citesc punctele
quick(1,n); //sortez punctele dupa y, iar in caz de egalitate dupa x
//ca sa pot lua cel mai de jos punct, si-n caz ca sunt
//mai multe, pe cel mai din stanga
infasuratoare;
if st[1]=st[k] then dec(k);
writeln(fo,k); //numarul de puncte de pe infasuratoare
for i:=1 to k do
writeln(fo,p[st[i]].x:16:6,' ', p[st[i]].y:16:6);
close(fi); close(fo);
end.