Cod sursa(job #502929)

Utilizator lianaliana tucar liana Data 20 noiembrie 2010 21:12:53
Problema Rays Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.91 kb
program rays;
type segment=record
  inc, sf:double;
end;
var f, g:text;
    v:array[1..2,0..200000] of segment;
    ac, n, x, y1, aux, y2, rez:longint;
    sf:double;

procedure citire;
var i:longint;
  begin
    readln(f,n);
    for i:=1 to n do
      begin
        read(f,x,y1,y2);
        if y1>y2 then
          begin
            aux:=y1;
            y1:=y2;
            y2:=aux;
          end;
        if x<0 then
          begin
            v[1,0].inc:=v[1,0].inc+1;
            v[1,trunc(v[1,0].inc)].inc:=y2/x;
            v[1,trunc(v[1,0].inc)].sf:=y1/x;
          end
         else
           begin
             v[2,0].inc:=v[2,0].inc+1;
             v[2,trunc(v[2,0].inc)].inc:=y1/x;
             v[2,trunc(v[2,0].inc)].sf:=y2/x;
           end;
      end;
  end;

function pozitionare(i,j:longint):longint;
var x:segment;
  begin
    x:=v[ac,i];
    while i<j do
      begin
        while (j>i) and (x.inc<=v[ac,j].inc) do
          j:=j-1;
        v[ac,i]:=v[ac,j];
        while (i<j) and (v[ac,i].inc<=x.inc) do
          i:=i+1;
        v[ac,j]:=v[ac,i];
      end;
    v[ac,i]:=x;
    pozitionare:=i;
  end;

procedure Qsort(st,dr:longint);
var m:longint;
  begin
    m:=pozitionare(st,dr);
    if st<m-1 then
      Qsort(st,m-1);
    if m+1<dr then
      Qsort(m+1,dr);
  end;

procedure rezolvare;
var i:longint;
  begin
    sf:=v[ac,1].sf;
    rez:=rez+1;
    for i:=2 to trunc(v[ac,0].inc) do
      begin
        if v[ac,i].inc>sf then
          begin
            rez:=rez+1;
            sf:=v[ac,i].sf;
          end;
        if v[ac,i].sf<sf then
          sf:=v[ac,i].sf;
      end;
  end;

  begin
    assign(f,'rays.in'); reset(f);
    assign(g,'rays.out'); rewrite(g);
    citire;
    for ac:=1 to 2 do
      begin
        Qsort(1,trunc(v[ac,0].inc));
        rezolvare;
      end;
   writeln(g,rez);

    close(f);
    close(g);
  end.