Cod sursa(job #203658)

Utilizator MciprianMMciprianM MciprianM Data 18 august 2008 11:59:00
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<fstream>
#include<algorithm>
using namespace std;
int a[1025], n;
int bsearch2(int st, int dr, int val){
  int m=(st+dr)/2;
  if(a[m]<val&&a[m+1]>=val) return m+1;
  if(a[m]<val&&a[m+1]<val)   return bsearch2(m+1,dr,val);
  if(a[m]>val)    return bsearch2(st,m-1,val);
  
}
int main(){
  int i, nrtri=0,j;
  ifstream f("nrtri.in");
  f>>n;
  for(i=1;i<=n;i++)
    f>>a[i];
  f.close();
  sort(a+1, a+n+1);
  for(i=1;i<n;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;
}