Cod sursa(job #486534)

Utilizator lianaliana tucar liana Data 21 septembrie 2010 21:36:15
Problema Trapez Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.64 kb
program trapez;
type punct=record
  x, y:int64;
end;
var f, g:text;
    n, ne, poz, lg, rez:int64;
    p:array[0..1000] of punct;
    v:array[0..1000000] of real;

procedure citire;
var i:longint;
  begin
    read(f,n);
    for i:=1 to n do
      read(f,p[i].x,p[i].y);
  end;

procedure generare;
var i, j:longint;
  begin
    for i:=1 to n do
      for j:=i+1 to n do
        begin
          ne:=ne+1;
          if p[i].x<>p[j].x then
            v[ne]:=(p[i].y-p[j].y)/(p[i].x-p[j].x)
           else
             v[ne]:=maxlongint;
        end;
  end;

function pozitionare(i,j:longint):longint;
var x:real;
  begin
    x:=v[i];
    while i<j do
      begin
        while (j>i) and (x<=v[j]) do
          j:=j-1;
        v[i]:=v[j];
        while (i<j) and (v[i]<=x) do
          i:=i+1;
        v[j]:=v[i];
      end;
    v[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 val:real;
  begin
    poz:=1;
    while poz<=ne do
      begin
        val:=v[poz];
        lg:=1;
        while {v[poz+1]=val}(abs(v[poz+1]-val)<=0.000000000000001) and (poz<ne) do
          begin
            lg:=lg+1;
            poz:=poz+1;
          end;
        rez:=rez+(lg*(lg-1)div 2);
        poz:=poz+1;
      end;
    writeln(g,rez);
  end;

  begin
    assign(f,'trapez.in'); reset(f);
    assign(g,'trapez.out'); rewrite(g);
    citire;
    generare;
    Qsort(1,ne);
    rezolvare;
    close(f);
    close(g);
  end.