Cod sursa(job #69526)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 3 iulie 2007 13:58:52
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<fstream.h>

unsigned int v[801];
int i, j, k, contor, n;

void citire()
{
  ifstream in("nrtri.in");
  in>>n;
  for(i=1; i<=n; i++)
    in>>v[i];
  in.close();
}

int cautare(int p, int u)
{
  int m;
  m=(p+u)/2;
  while (p<=u) 
    {
      if ((v[m]<=v[i]+v[j] && v[m+1]>v[i]+v[j]) || (v[m]<=v[i]+v[j] && m==n)) return m;
        else if (v[m]<=v[i]+v[j] && v[m+1]+v[j]<=v[i]+v[j]) {p=m+1; m=(p+u)/2;}
	       else {u=m-1; m=(p+u)/2;}
    }
  return 0;
}
  
void prelucr()
{
  for (i=1; i<n-1; i++)
    for (j=i+1; j<n; j++)
      {
 	k=cautare(j+1,n);
	if (k) contor+=(k-j);
      }
	 
  ofstream out("nrtri.out");
  out<<contor;
  out.close();
}
 
int main()
{
   citire();
   prelucr();
   return 0;
}