Cod sursa(job #203645)

Utilizator MciprianMMciprianM MciprianM Data 18 august 2008 10:01:57
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<fstream>
#include<algorithm>
using namespace std;
int a[1024], n;
int bsearch2(int st, int dr, int val){
  int k=st,pas=1,i;
  while(a[k]<=val&&(k<<1)<=dr)  k<<=1,pas<<=1;
  for(i=k;i>=(k>>1);pas>>=1)
    if(i-pas>val&&i-pas<=(k>>1))
      i-=pas;
  return i;
}
int main(){
  int i, nrtri=0,j;
  ifstream f("nrtri.in");
  f>>n;
  for(i=0;i<=n;i++)
    f>>a[i];
  f.close();
  sort(a, a+n);
  for(i=0;i<n-1;i++)
    for(j=i+1;j<n;j++)
      nrtri+=(n-bsearch2(j,n-1,a[i]+a[j]));
  ofstream g("nrtri.out");
  g<<nrtri<<'\n';
  g.close();
  return 0;
}