Cod sursa(job #305311)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 16 aprilie 2009 22:13:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
#define max 3000
int x,m,nr=0,n,k,v[max+1];
#define Nmax 500005
void quick_sort (int st,int dr)
{
    int i=st,j=dr,piv=v[(st+dr)/2],aux;
    do
    {
        while (v[i]<piv) 
            ++i;
        while (v[j]>piv) 
            --j;
        if (i<=j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            ++i; 
            --j;    
        }
    } 
    while (i<=j);
    if (st<j)
        quick_sort(st,j);
    if (i<dr) 
        quick_sort(i,dr);    
}

int main()
{int i,j;
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
	    scanf("%d",&x);
       for(i=1;i<=x;i++)
	       scanf("%d",&v[i]);
   quick_sort(1,x);
       for(i=1;i<=x-2;++i)   
    {   
        k=i+2;   
        for(j=i+1;j<=x-1;++j)   
        {   
            while(k<=x && v[i]+v[j]>=v[k])   
                ++k;   
            nr+=k-j-1;//k=indicele primului care nu e bun=>toate cele dintre j+1 si k-1 sunt bune   
        }   
    }   
    printf("%d\n",nr);   

     
   return 0;

}