Cod sursa(job #923988)

Utilizator andrei_toaderToader Andrei Sorin andrei_toader Data 24 martie 2013 00:01:01
Problema Infasuratoare convexa Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 2.03 kb
program deyu;
const fi='infasuratoare.in';
      fo='infasuratoare.out';
      pi=3.14159265;
type rec=record
x,y,dist,up:extended;
end;
var f,g:text;
p:array[0..120000] of rec;
s:array[1..50000] of rec;
o:extended;
bufin,bufout:array[1..65000] of byte;
var n,i,j,min,vf:longint;
function pivot(st,dr:longint):longint;
var r,d,di:longint;
aux:rec;
begin
r:=st;
d:=dr;
di:=1;
while r<d do
   begin
   if p[r].up>=p[d].up then
       begin
       aux:=p[r];
       p[r]:=p[d];
       p[d]:=aux;
       di:=-di;
       end;
   if di<0 then
   dec(d) else
   inc(r);
   end;
   pivot:=r;
end;
procedure sort(st,dr:longint);
var p1:longint;
begin
if st<dr then
   begin
   p1:=pivot(st,dr);
   sort(st,p1-1);
   sort(p1+1,dr);
   end;
end;
procedure add(t:rec);
begin
inc(vf);
s[vf]:=t;
end;
procedure del;
begin
dec(vf);
end;
function produs(p1,p2,p3:rec):real;
begin
produs:=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
end;
begin
assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
settextbuf(f,bufin);
settextbuf(g,bufout);
read(f,n);
min:=0;
p[0].x:=maxlongint;
p[0].y:=maxlongint;
for i:=1 to n do
begin
read(f,p[i].x,p[i].y);
if p[i].y<p[min].y then
min:=i
else
if p[i].y=p[min].y then
    if p[i].x<p[min].x then
       min:=i;
end;
for i:=1 to n do
if i<>min then
   begin
   p[i].dist:=sqrt(sqr(p[i].x-p[min].x)+sqr(p[i].y-p[min].y));
   if p[i].x-p[min].x<>0 then
   begin
   p[i].up:=arctan(((p[i].y-p[min].y)/(p[i].x-p[min].x)));
   p[i].up:=p[i].up*(180/pi)
   end
   else
   p[i].up:=90;
   if p[i].up<0 then
      p[i].up:=180+p[i].up;
      end;
sort(1,n);
vf:=0;
add(p[1]);
add(p[2]);
for i:=3 to n do
  begin
  o:=produs(s[vf-1],s[vf],p[i]);
  if o=0 then
  begin
  del;
  add(p[i]);
  end
  else
  if o>0 then
  add(p[i])
  else
  begin
  while (o<=0)and(vf>1) do
  begin
  del;
  o:=produs(s[vf-1],s[vf],p[i]);
  end;
  add(p[i]);
  end;
  end;
writeln(g,vf);
for i:=1 to vf do
writeln(g,s[i].x:10:6,' ',s[i].y:10:6);
close(f);
close(g);
end.