Cod sursa(job #263316)

Utilizator irene_mFMI Irina Iancu irene_m Data 20 februarie 2009 10:10:56
Problema Infasuratoare convexa Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 2.24 kb
type t=record
     x,y,u:real;
     end;
var p,sol:array[0..30]of t;
f,g:text;
 min:real;
 i,n,m:integer;

function angle2(cx,cy:real):real;
var xcm,ycm,sinus,cosinus:real;
begin
xcm:=p[0].x;ycm:=p[0].y;
sinus:=(cy-ycm)/sqrt(sqr(cy-ycm)+sqr(cx-xcm));
cosinus:=(cx-xcm)/sqrt(sqr(cy-ycm)+sqr(cx-xcm));
if cosinus=0 then
begin
if sinus>0 then angle2:=pi/2 else if sinus<0 then angle2:=3*pi/2 end
else
 begin
if (sinus>0) and (cosinus>0) then
angle2:=arctan(sinus/cosinus);
if (sinus>0) and (cosinus<0) then
angle2:=pi-arctan(abs(sinus/cosinus));
if (sinus<=0) and (cosinus<0) then
angle2:=pi+arctan(abs(sinus/cosinus));
if (sinus<=0) and (cosinus>0) then
angle2:=2*pi-arctan(abs(sinus/cosinus));
end;
end;
procedure citire;
begin
assign(f,'infasuratoare.in');reset(f);
readln(f,n);
readln(f,p[0].x,p[0].y);
for i:=1 to n-1 do
begin
readln(f,p[i].x,p[i].y);
p[i].u:=angle2(p[i].x,p[i].y);
end;
 close(f);
 end;
 procedure minim;
var i:integer;
begin
min:=p[0].y;
 for i:=1 to n-1 do
   if p[i].y<min then
   min:=p[i].y;
end;

procedure translatie;
var i:integer;
begin
  for i:=1 to n-1 do
  p[i].y:=p[i].y-min;
end;

procedure sortare;
var i:integer; sw:boolean; aux:t;
begin
sw:=true;
  while sw=true do
  begin
  sw:=false;
     for i:=1 to n-2 do
       if p[i].u>p[i+1].u then
       begin
       aux:=p[i];
       p[i]:=p[i+1];
       p[i+1]:=aux;
       sw:=true;
       end;
   end;
end;

function arie(x1,x2,x3,y1,y2,y3:real):real;
var x:real;
begin
x:=x1*y2+x2*y3+y1*x3-x3*y2-y3*x1-x2*y1;
arie:=x;
end;

procedure infasuratoare;
var i:integer;
begin
m:=1;sol[0]:=p[0];
for i:=1 to n-1 do
begin
if m=1 then
begin
sol[m]:=p[i];
m:=m+1;
end
else
begin
   while (m>=2) and
   (arie(p[i].x,sol[m-1].x,sol[m-2].x,p[i].y,sol[m-1].y,sol[m-2].y)>0) do
    m:=m-1;
    sol[m]:=p[i];
     m:=m+1;
  end;
 end;
end;

procedure afisare;
var i:integer;
begin
assign(g,'infasuratoare.out');rewrite(g);
writeln(g,m);
for i:=0 to m-1 do
writeln(g,sol[i].x:6:6,' ',sol[i].y+min:6:6);
close(g);
end;

procedure retranslatare;
var i:integer;
begin
for i:=1 to m do
sol[i].y:=sol[i].y+min;
end;

begin
citire;
minim;
translatie;
sortare;
infasuratoare;
afisare;
end.