Cod sursa(job #730487)

Utilizator Buzu_Tudor_RoCont vechi Buzu_Tudor_Ro Data 6 aprilie 2012 13:06:31
Problema Infasuratoare convexa Scor 50
Compilator fpc Status done
Runda Arhiva educationala Marime 2.82 kb
Program convex_algoritm_graham;
type point=record
           x,y : extended;
           end;
var fi,fo : text;
    i,n,poz : longint; px,py,q:extended;
    a:array[0..120000] of point;
    p:array[0..120000] of extended;
    t:array[0..120000] of longint; t2:point;

Function sarrus(p1,p2,p3:point):extended;
begin
    sarrus:=p1.x*p2.y+p2.x*p3.y+p3.x*p1.y
           -p2.y*p3.x-p3.y*p1.x-p1.y*p2.x;
end;

Function polar(x,y:extended):extended;
begin
    if x>0 then begin
                if y>0 then polar:=arctan(y/x)
                       else polar:=arctan(y/x)+2*pi;
                end
           else if x<0 then polar:=arctan(y/x)+pi
                       else if x=0 then begin
                                        if y>0 then polar:=pi/2
                                               else if y<0 then polar:=3*pi/2
                                                           else polar:=0;
                                        end;
end;

Procedure quick(left,right:longint);
var i,j:longint;  r:extended;
begin
    r:=p[(left+right) div 2];
    i:=left; j:=right;

    while i<j do begin
          while p[i]<r do i:=i+1;
          while p[j]>r do j:=j-1;
          if i<=j then begin
                       t2:=a[i]; a[i]:=a[j]; a[j]:=t2;
                       q:=p[i]; p[i]:=p[j]; p[j]:=q;
                       i:=i+1; j:=j-1;
                       end;
                 end;

    if j>left then quick(left,j);
    if i<right then quick(i,right);
end;

begin
    assign(fi,'infasuratoare.in'); reset(fi); readln(fi,n);
    assign(fo,'infasuratoare.out'); rewrite(fo); readln(fi,a[1].x,a[1].y);
    px:=a[1].x; py:=a[1].y;
    for i:=2 to n do begin
                     readln(fi,a[i].x,a[i].y);
                     if a[i].y<py then begin py:=a[i].y; px:=a[i].x; end;
                     end;


    for i:=1 to n do p[i]:=polar(a[i].x-px,a[i].y-py);
    quick(1,n);   poz:=2; t[1]:=1; t[2]:=2;

    for i:=3 to n do begin
                     if sarrus(a[t[poz-1]],a[i],a[t[poz]])<0 then begin
                                                                  poz:=poz+1;
                                                                  t[poz]:=i;
                                                                  end
                                                             else begin
                                                                  while sarrus(a[t[poz-1]],a[i],a[t[poz]])>0 do poz:=poz-1;
                                                                  poz:=poz+1;
                                                                  t[poz]:=i;
                                                                  end;
                     end;
    writeln(fo,poz);
    for i:=1 to poz do writeln(fo,a[t[i]].x:0:6,' ',a[t[i]].y:0:6);
    close(fi); close(fo);
end.