Cod sursa(job #458767)

Utilizator lianaliana tucar liana Data 26 mai 2010 09:35:06
Problema Numarare triunghiuri Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 2 kb
program nrtri;
var f, g:text;
    std, sts, rez, n, st, dr, x, pozinc, pozsf:longint;
    v:array[1..800] of longint;

procedure citire;
var i:longint;
  begin
    readln(f,n);
    for i:=1 to n do
      read(f,v[i]);
  end;

function pozitionare(i,j:longint):longint;
var x:longint;
  begin
    x:=v[i];
    while i<j do
      begin
        while (j>i) and (v[j]>=x) 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(sts,drs:longint);
var m:longint;
  begin
    m:=pozitionare(sts,drs);
    if sts<m-1 then
      Qsort(sts,m-1);
    if m+1<drs then
      Qsort(m+1,drs);
  end;

procedure cautare_suma;
var m:longint;
  begin
{    st:=1;}
    dr:=n;
    while sts<=dr do
      begin
        m:=(sts+dr) div 2;
        if v[m]<=x then
          sts:=m+1
         else
           dr:=m-1;
      end;
    pozsf:=dr;
    sts:=dr;
  end;

procedure cautare_diferenta;
var m:longint;
  begin
{    std:=1;    }
    dr:=n;
    while std<=dr do
      begin
        m:=(std+dr) div 2;
        if v[m]>=x then
          dr:=m-1
         else
           std:=m+1;
      end;
    pozinc:=std;
  end;

procedure rezolvare;
var i, j, nr:longint;
  begin
    for i:=1 to n do
      begin
        sts:=1;
        std:=1;
        for j:=i+1 to n do
          begin
            x:=v[i]+v[j];
            cautare_suma;
            x:=abs(v[i]-v[j]);
            cautare_diferenta;
            nr:=pozsf-pozinc+1;
            if (i>=pozinc) and (i<=pozsf) then
              nr:=nr-1;
            if (j>=pozinc) and (j<=pozsf) then
              nr:=nr-1;
            if nr>0 then
              rez:=rez+nr;
          end;
      end;
    writeln(g,rez div 3);
  end;

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