Cod sursa(job #115293)

Utilizator h_istvanHevele Istvan h_istvan Data 16 decembrie 2007 12:03:52
Problema Rays Scor 40
Compilator fpc Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 2.91 kb
program rays;
type szakasz = record
               p1,p2:real;
               end;
var f:text;
    n,x,y1,y2,i,j,e1,e2:longint;
    s1,s2:real;
    v:array[1..200000] of szakasz;

procedure qsort1(bal,jobb:word);
var i,j:longint;
    va:real;
    cs:szakasz;
begin
     i:=bal;
     j:=jobb;
     va:=v[(i+j) div 2].p2;
     while(i<=j) do
     begin
          while v[i].p2 < va do inc(i);
          while v[j].p2 > va do dec(j);
          if(i<=j) then
          begin
               cs:=v[i];
               v[i]:=v[j];
               v[j]:=cs;
               inc(i);dec(j);
          end;
     end;
     if(bal < j) then qsort1(bal,j);
     if(i < jobb) then qsort1(i,jobb);
end;

procedure qsort2(bal,jobb:word);
var i,j:longint;
    va:real;
    cs:szakasz;
begin
     i:=bal;
     j:=jobb;
     va:=v[(i+j) div 2].p1;
     while(i<=j) do
     begin
          while v[i].p1 > va do inc(i);
          while v[j].p1 < va do dec(j);
          if(i<=j) then
          begin
               cs:=v[i];
               v[i]:=v[j];
               v[j]:=cs;
               inc(i);dec(j);
          end;
     end;
     if(bal < j) then qsort2(bal,j);
     if(i < jobb) then qsort2(i,jobb);
end;


function metsz(p,k,v:real):boolean;
var control:boolean;
begin
     if(p>k) and (p<v) then control:=true
                       else control:=false;
     if(k > 3*pi/2) and (v < pi/2) then control:=not control;
     metsz:=control;
end;

begin
     assign(f,'rays.in');
     reset(f);
     readln(f,n);
     for i:=1 to n do
     begin
          readln(f,x,y1,y2);
          s1:=arctan(y1/x);
          s2:=arctan(y2/x);
          if(x<0) then
          begin
               s1:=s1+pi;
               s2:=s2+pi;
          end else
          if(x>0) and (y1<0) then s1:=s1+2*pi;
          if(x>0) and (y2<0) then s2:=s2+2*pi;

          if(x>0) and ((y1<0) and (y2>0)) then
          begin
               v[i].p1:=s1;
               v[i].p2:=s2;
          end else
          if(x>0) and ((y1>0) and (y2<0)) then
          begin
               v[i].p1:=s2;
               v[i].p2:=s1;
          end else if(s1<s2) then
          begin
               v[i].p1:=s1;
               v[i].p2:=s2;
          end else
          begin
               v[i].p1:=s2;
               v[i].p2:=s1;
          end;
     end;
     close(f);

     qsort1(1,n);

     i:=1;
     e1:=0;
     while(i<=n) do
     begin
          e1:=e1+1;
          j:=i;
          i:=i+1;
          while(metsz(v[j].p2,v[i].p1,v[i].p2)) and (i<=n) do i:=i+1;
     end;

     qsort2(1,n);

     i:=1;
     e2:=0;
     while(i<=n) do
     begin
          e2:=e2+1;
          j:=i;
          i:=i+1;
          while(metsz(v[j].p1,v[i].p1,v[i].p2)) and (i<=n) do i:=i+1;
     end;

     if(e2<e1) then e1:=e2;

     assign(f,'rays.out');
     rewrite(f);
     writeln(f,e1);
     close(f);
end.