Cod sursa(job #91987)

Utilizator 100puncteIonut Popa 100puncte Data 14 octombrie 2007 02:23:17
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
/*
100 p
*/
#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[i]+v[j]) {p=m+1; m=(p+u)/2;}
	       else {u=m-1; m=(p+u)/2;}
    }
  return 0;
}

void buble()
{
  int aux, ok=1;
  while(ok)
    {
      ok=0;
      for (i=1; i<n; i++)
	if (v[i]>v[i+1])
	  {
	    aux=v[i];
	    v[i]=v[i+1];
	    v[i+1]=aux;
	    ok=1;
	  }
    }
}

  
void prelucr()
{
  buble();
  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;
}