Cod sursa(job #118)

Utilizator wefgefAndrei Grigorean wefgef Data 5 decembrie 2006 13:56:44
Problema Triang Scor 90
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.54 kb
program triang;
var f :text;
    vx, vy :array[1..1500] of real;
    n :integer;

procedure read_data; inline;
var i:integer;
begin
  assign(f,'triang.in');reset(f);
     read(f,n);
     for i:=1 to n do read(f,vx[i],vy[i]);
  close(f);
end;

function egal(a,b:real):boolean;
begin
   egal:=abs(a-b)<0.001;
end;

{-------------------------------------------------------------------------}
procedure part(st,dr:integer; var m:integer); inline;
var i,j:integer;
    scx,scy,aux:real;
begin
   scx:=vx[st]; scy:=vy[st];
   i:=st-1; j:=dr+1;
   while i<j do begin
      repeat inc(i) until (vx[i]>scx) or ((vx[i]=scx) and (vy[i]>=scy));
      repeat dec(j) until (vx[j]<scx) or ((vx[j]=scx) and (vy[j]<=scy));
      if i<j then begin
        aux:=vx[i]; vx[i]:=vx[j]; vx[j]:=aux;
        aux:=vy[i]; vy[i]:=vy[j]; vy[j]:=aux;
      end;
   end;
   m:=j;
end;

procedure quick(st,dr:integer); inline;
var m:integer;
begin
   if st<dr then begin
      part(st,dr,m);
      quick(st,m);
      quick(m+1,dr);
   end;
end;
{-------------------------------------------------------------------------}

function maimic(m:integer; x,y:real):boolean; inline;
begin
  if egal(vx[m],x) then begin
     if vy[m]<y then maimic:=true
                else maimic:=false;
     exit;
  end;
  if vx[m]<x then maimic:=true
             else maimic:=false;
end;

function este(st,dr:integer; x,y:real):boolean; inline;
var m:integer;
begin
   if st>dr then begin
      este:=false;
      exit;
   end;
   m:=(st+dr) div 2;
   if (egal(vx[m],x)) and (egal(vy[m],y)) then begin
      este:=true;
      exit;
   end;
   if maimic(m,x,y) then este:=este(m+1,dr,x,y)
                    else este:=este(st,m-1,x,y);
end;

procedure solve; inline;
var i, j :integer;
    sum :longint;
    x, y, cos60, sin60, cos300, sin300 :real;
begin
   sum:=0;
   cos60:=cos(pi/3); cos300:=cos60;
   sin60:=sin(pi/3); sin300:=-sin60;
   quick(1,n);
   for i:=1 to n-2 do
   for j:=i+1 to n-1 do begin

      x:=vx[i]+(vx[j]-vx[i])*cos60-(vy[j]-vy[i])*sin60;
      y:=vy[i]+(vx[j]-vx[i])*sin60+(vy[j]-vy[i])*cos60;
      if (x>vx[j]) or ((vx[j]=x) and (y>vy[j])) then
      if este(j+1,n,x,y) then inc(sum);

      x:=vx[i]+(vx[j]-vx[i])*cos300-(vy[j]-vy[i])*sin300;
      y:=vy[i]+(vx[j]-vx[i])*sin300+(vy[j]-vy[i])*cos300;
      if (x>vx[j]) or ((vx[j]=x) and (y>vy[j])) then
      if este(j+1,n,x,y) then inc(sum);

   end;

   assign(f,'triang.out');rewrite(f);
      writeln(f,sum);
   close(f);
end;

begin
  read_data;
  solve;
end.