Cod sursa(job #283731)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 19 martie 2009 17:22:47
Problema Infasuratoare convexa Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 2.02 kb


var n,m,i,j,nst, p1, p2,c1,c2:integer;
    mx,my:real;
    x,y: array[1..120000000] of real;
    f: text;
    st: array [0..120000000] of integer;


procedure Sort(l, r: Integer);
var
  i, j, a: integer;
  yy: real;
begin
  i := l; j := r; a := (l+r) DIV 2;
  repeat
    while y[i]*x[a] < y[a]*x[i] do i := i + 1;
    while y[a]*x[j] < y[j]*x[a] do j := j - 1;
    if i <= j then
    begin
      yy := x[i]; x[i] := x[j]; x[j] := yy;
      yy := y[i]; y[i] := y[j]; y[j] := yy;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

function dist (p1,p2 : integer): real;
begin
dist:= sqr(x[p1]-x[p2]) + sqr(y[p1]-y[p1]);
end;

begin
assign  (f,'infasuratoarea.in');
reset   (f);
readln  (f,n);
mx :=  2000000000;
my :=  2000000000;
for i:=1 to n do
    begin
    readln (f, x[i], y[i]);
    if y[i]<my then
       begin
            my:= y[i];
            mx:= x[i];
       end
       else
           if (my=y[i]) and (x[i]<mx) then
              mx := x[i];
    end;

for i:=1 to n do
    begin
    y[i] := y[i] - my;
    x[i] := x[i] - mx;
    end;
close   (f);

Sort(2,n);

nst:=2;
st[1]:=1;
st[2]:=2;

for i:=3 to n do
    begin
    while (nst>1) and ((x[st[nst]]-x[st[nst-1]])*(y[i]-y[st[nst-1]]) + (x[i]-x[nst-1])*(y[st[nst-1]]-y[st[nst]]) < 0 )do
          dec(nst);
    inc(nst);
    st[nst]:=i;
    end;
assign(f,'infasuratoarea.out');
rewrite(f);

writeln(f,nst);
for i:=1 to nst do
    writeln(f,x[st[i]]+mx:0:6,' ',y[st[i]]+my:0:6);
close(f);

{
p1:=1; p2:=1;
while (p2<nst) and (dist(st[p1],st[p2]) < dist(st[p1],st[p2+1])) do inc(p2);

c1:=p1; c2:=p2;
while (p2<nst) do
      begin
      inc(p1);
      while (p2<nst) and (dist(st[p1],st[p2]) < dist(st[p1],st[p2+1])) do
            begin
            inc(p2);
            if dist(st[c1],st[c2])< dist(st[p1],st[p2]) then
               begin
               c1:=p1;
               c2:=p2;
               end;
            end;
      end;
}
end.