Cod sursa(job #724533)

Utilizator amaliutzzaGoia Amalia amaliutzza Data 26 martie 2012 17:10:07
Problema Infasuratoare convexa Scor 90
Compilator fpc Status done
Runda Arhiva educationala Marime 2.53 kb
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,ax,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;
                    ax:=ai; ai:=bi; bi:=ax;
                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
             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.