Cod sursa(job #1412575)

Utilizator casianos1996Marc Casian Nicolae casianos1996 Data 1 aprilie 2015 12:54:04
Problema Infasuratoare convexa Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.73 kb
program infasuratoare_convexa_pregatire_oni;

type    pct=record
        x,y:real;
end;

var     f,g:text;
        h,n,i,j,k,q:longint;
        v:array[1..120000] of pct;
        ok:array[1..120000] of 0..1;
        stiva:array[1..120000] of longint;
        bufin,bufout:array[1.. 1 shl 16] of byte;

function  pivot(st,dr:longint):longint;
var       di,dj,i,j,aux:longint;
          auxx:pct;
begin
  i:=st; j:=dr;
  di:=0; dj:=1;
  while i<j do
    begin
      if (v[i].x>v[j].x) or ((v[i].x=v[j].x) and (v[i].y>v[j].y)) then
        begin
          aux:=di;
          di:=dj;
          dj:=aux;
          auxx:=v[i];
          v[i]:=v[j];
          v[j]:=auxx;
        end;
      i:=i+di;
      j:=j-dj;
    end;
  pivot:=i;
end;

procedure sort(st,dr:longint);
var       p:longint;
begin
  if st<dr then
    begin
      p:=pivot(st,dr);
      sort(st,p-1);
      sort(p+1,dr);
    end;
end;

function det(a,b,c:pct):real;
begin
  det:=a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-a.x*c.y-a.y*b.x;
end;

begin
  assign(f,'infasuratoare.in'); reset(f);
  assign(g,'infasuratoare.out'); rewrite(g);
  readln(f,n);
  for i:=1 to n do
    readln(f,v[i].x,v[i].y);
  sort(1,n);
  stiva[1]:=1; stiva[2]:=2; q:=1; k:=2; i:=3;
  ok[stiva[2]]:=1;
  while ok[1]=0 do
    begin
      while ok[i]=1 do
        begin
          if i=n then q:=-1;
          i:=i+q;
        end;
      while (k>=2) and (det(v[stiva[k-1]],v[stiva[k]],v[i])<0) do
        begin
          ok[stiva[k]]:=0;
          dec(k);
        end;
      inc(k);
      stiva[k]:=i;
      ok[i]:=1;
    end;
  h:=k-1;
  writeln(g,h);
  for i:=1 to h do
    writeln(g,v[stiva[i]].x:0:6,' ',v[stiva[i]].y:0:6);
  close(f);
  close(g);
end.