Cod sursa(job #363680)

Utilizator cristinabCristina Brinza cristinab Data 14 noiembrie 2009 10:27:31
Problema Infasuratoare convexa Scor 50
Compilator fpc Status done
Runda Arhiva educationala Marime 2.94 kb
type punct=record
           x,y:real;
           end;

var p:array[0..120000] of punct;
    s:array[1..120000] of punct;
    polar:array[1..120000] of real;
    n,varf,poz:longint;
    xmin,ymin:real;

procedure citire;
var i:longint;
begin
assign(input,'infasuratoare.in'); reset(input);
readln(n);
for i:=1 to n do readln(p[i].x,p[i].y);
close(input);
end;

procedure varf_minim;
var i:longint;
begin

xmin:=maxlongint;
ymin:=maxlongint;

for i:=1 to n do
    if p[i].x<xmin then
       begin
       ymin:=p[i].y;
       xmin:=p[i].x;
       poz:=i;
       end
    else if (p[i].x=xmin) and (p[i].y<ymin) then
            begin
            ymin:=p[i].y;
            poz:=i;
            end;

p[0].x:=xmin;
p[0].y:=ymin;

end;


procedure eliminare;
var i:longint;
begin

for i:=poz+1 to n do p[i-1]:=p[i];
dec(n);

end;


procedure formare;
var i:longint;
    x,y,r:real;
begin
for i:=1 to n do
    if p[i].x<>p[0].x then polar[i]:=arctan((p[i].y-p[0].y)/(p[i].x-p[0].x))
                      else polar[i]:=maxlongint;
end;

function dist(a,b:punct):real;
var x,y:real;
begin
x:=sqr(a.x-b.x);
y:=sqr(a.y-b.y);
dist:=sqrt(sqr(x)+sqr(y));
end;


procedure qsort(l,r:longint);
var i,j:longint;
    aux1:punct;
    v,aux:real;
begin

i:=l;
j:=r;
v:=polar[(l+r) div 2];

repeat
 while polar[i]<v do inc(i);
 while v<polar[j] do dec(j);
 if i<=j then

    begin

    if polar[i]<>polar[j] then

    begin
    aux:=polar[i];
    polar[i]:=polar[j];
    polar[j]:=aux;
    aux1:=p[i];
    p[i]:=p[j];
    p[j]:=aux1;
    end

    else if (polar[i]=polar[j]) and (dist(p[0],p[i])>dist(p[0],p[j])) then
            begin
            aux1:=p[i];
            p[i]:=p[j];
            p[j]:=aux1;
            end;

    inc(i);
    dec(j);
    end;


until i>=j;

if j>l then qsort(l,j);
if i<r then qsort(i,r);
end;

function produs_incrucisat(p1,p2,p3:punct):real;
begin
produs_incrucisat:=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
end;

procedure introducere(p1:punct);
begin
inc(varf);
s[varf]:=p1;
end;

procedure scanare_graham;
var i:integer;
    prod:real;
begin
varf:=0;
introducere(p[0]);
introducere(p[1]);
for i:=2 to n do
    begin
    prod:=produs_incrucisat(s[varf-1],s[varf],p[i]);
    if prod=0 then
       begin
       dec(varf);
       introducere(p[i]);
       end
    else if prod>0 then introducere(p[i])
    else begin
         while (prod<=0) and (varf>1) do
               begin
               dec(varf);
               prod:=produs_incrucisat(s[varf-1],s[varf],p[i]);
               end;
         introducere(p[i]);
         end;
    end;
end;

procedure afisare;
var i:longint;
begin
assign(output,'infasuratoare.out');rewrite(output);
writeln(varf);
for i:=1 to n do writeln(s[i].x:2:12,' ',s[i].y:2:12);
close(output);
end;

begin
citire;
varf_minim;
eliminare;
formare;
qsort(1,n);
scanare_graham;
afisare;
end.