Cod sursa(job #609556)

Utilizator ion824Ion Ureche ion824 Data 22 august 2011 11:18:52
Problema Numarare triunghiuri Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<fstream>
using namespace std;
const short nmax=800;
short a[nmax+1],k;

void qsort(short lb,short ub){
     short i=lb,j=ub,p=a[(i+j)>>1];      
     do{
        while(a[i]<p)++i;
        while(a[j]>p)--j;   
        if(i<=j){
          k=a[i]; a[i]=a[j]; a[j]=k; ++i; --j; 
        }
     }while(i<=j);
   if(j>lb)qsort(lb,j);
   if(ub>i)qsort(i,ub);                
}

short cautare_bin(short val,short left,short right){
      short m;
      while(left<right){
          m=(left+right)/2+1;
          if(a[m]<=val)left=m; 
            else right=m-1;
      }
      if(a[left]<=val) return left;
      return left-1;                                
}

int main(void){
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");
    short i,j,nr=0,n;
    fin>>n;
    for(i=0;i<n;++i)fin>>a[i]; fin.close();
    qsort(0,n-1); 
    for(i=0;i<n-2;++i)
      for(j=i+1;j<n-1;++j)
        nr+=cautare_bin(a[i]+a[j],j+1,n-1)-j;    
    fout<<nr; fout.close();
 return 0;   
}