Cod sursa(job #293030)

Utilizator 05_YohnE1 La5c01 05_Yohn Data 31 martie 2009 21:35:01
Problema Infasuratoare convexa Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.77 kb
type punct=record
           x,y:double;
           end;

var v:array[1..120001]of punct;
    pct:punct;
    det:real;
    st:array[1..120001]of longint;
    ung:array[1..120001]of double;
    n,i,j,poz,u:longint;

procedure sort(l,r:longint);
var aux1:punct;
    aux,y:double;
    st,dr,x:longint;
begin
st:=l; dr:=r;
x:=(l+r)div 2;
y:=ung[x];
repeat
while ung[st]<y do inc(st);
while ung[dr]>y do dec(dr);
if st<=dr then begin
   aux:=ung[st]; ung[st]:=ung[dr]; ung[dr]:=aux;
   aux1:=v[st]; v[st]:=v[dr]; v[dr]:=aux1;
   inc(st);dec(dr);
   end;
until st>dr;
if l<dr then sort(l,dr);
if st<r then sort(st,r);
end;

function determinant(a,b,c:punct):boolean;
begin
determinant:=(a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y) < 0;
end;


begin
assign(input,'infasuratoare.in');reset(input);
assign(output,'infasuratoare.out');rewrite(output);
read(n);
read(v[1].x,v[1].y);
pct:=v[1]; poz:=1;
for i:=2 to n do begin
    read(v[i].x,v[i].y);
    if v[i].y<pct.y then begin
                         pct:=v[i];
                         poz:=i;
                         end
                    else if (v[i].y=pct.y)and(v[i].x<pct.x)then begin
                            pct:=v[i];
                            poz:=i;
                            end;

    end;
for i:=1 to n do
    if i<>poz then begin
       if v[i].x-pct.x<>0 then ung[i]:=arctan((v[i].y-pct.y)/(v[i].x-pct.x))
                          else ung[i]:=pi/2;
       if ung[i]<0 then ung[i]:=ung[i]+pi;
    end;

sort(1,n);

u:=1;
st[1]:=1;
for i:=2 to n do begin
    while (u>=2)and(determinant(v[st[u-1]],v[st[u]],v[i]))do dec(u);
    inc(u);
    st[u]:=i;
end;
writeln(u);
for i:=1 to u do writeln(v[st[i]].x:0:6,' ',v[st[i]].y:0:6);
close(output);
end.