Cod sursa(job #160726)

Utilizator testelatugelu testelatu testelatu Data 16 martie 2008 19:09:02
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>
#include<algorithm>
#define nmax 900
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

int a[nmax];

int cautare(int st,int dr,int sum){
    
int m,poz=st;
    
    while( st<=dr )
{
     m=(st+dr)/2;
         
     if( a[m]<=sum ){
     poz=max(m,poz);//just to be sure
     st=m+1;
     }
     else
     dr=m-1;
     
}
 
return poz;

}

int main()
{
 freopen("nrtri.in","r",stdin);
 freopen("nrtri.out","w",stdout);
 
 int n,i;
 scanf("%d",&n);
    
    for(i=1; i<=n; ++i)
    scanf("%d",&a[i]);
    
    sort(a+1,a+n+1);
    
 int sol=0,sum,j;

    for(i=1; i<=n-2; ++i)
        for(j=i+1; j<=n-1; ++j){
        sum=a[i]+a[j];
               
               if( a[j+1]<=sum)
               sol+=(cautare(j+1,n,sum)-j); 

        }
    
    printf("%d\n",sol);
    
    
    return 0;
}