Cod sursa(job #680848)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 15 februarie 2012 23:43:47
Problema Infasuratoare convexa Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.59 kb
Program inf_convexa;
 type tip=record
       x,y,pl:real;
       end;
 var a,st:array [1..120000] of tip;
     p1:tip;
     b1,b2:array [1..1 shl 15] of char;
     i,j,n,l:longint;
     fi,fo:text;
procedure sort(l,r:longint);
 var i,j:longint;
     k:real;
     y:tip;
 begin
  i:=l; j:=r;
   k:=a[(l+r) div 2].pl;
 repeat
  while a[i].pl<k do inc(I);
   while a[j].pl>k do dec(j);
 if i<=j then
              begin
               y:=a[i];
                a[i]:=a[j];
                  a[j]:=y;
                     inc(i); dec(j);
              end;
 until i>=j;
  if l<j then sort(l,j);
   if i<r then sort(i,r);
end;
begin
 assign(fi,'infasuratoare.in');
  assign(fo,'infasuratoare.out');
 settextbuf(fi,b1); settextbuf(fo,b2);
 reset(fi); rewrite(fo); readln(fi,n); p1.x:=10000000; p1.y:=10000000;
 for i:=1 to n do begin
                    readln(fi,a[i].x,a[i].y);
                    if (a[i].x<p1.x) or ((a[i].x=p1.x) and (a[i].y<p1.y)) then p1:=a[i];
                   end;
 st[1]:=p1;
 for i:=1 to n do
  if (a[i].x=p1.x) and (a[i].y=p1.y) then  a[i].pl:=-10000000
               else if a[i].x<>p1.x then a[i].pl:=arctan((a[i].y-p1.y)/(a[i].x-p1.x))
                else a[i].pl:=10000000;
 sort(1,n);
  st[2]:=a[2]; l:=2;
 for i:=3 to n do begin
                   while (l>=2) and (st[l-1].x*st[l].y+st[l].x*a[i].y+a[i].x*st[l-1].y-st[l-1].x*a[i].y-st[l].x*st[l-1].y-a[i].x*st[l].y<0) do dec(l);
                    inc(l); st[l]:=a[i];
                   end;
 writeln(fo,l);
  for i:=1 to l do writeln(fo,st[i].x:0:6,' ',st[i].y:0:6);
 close(fo);
end.