Mai intai trebuie sa te autentifici.

Cod sursa(job #304300)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 11 aprilie 2009 22:34:27
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#define max 3000
int x,m,nr=0,n,k,b,a,v[max+1],in[max],poza,pozb;
#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 caut(int m,int k)
{ int lo=1,i,j,hi=x,mid;
while(lo<=hi)

       {
	 mid=lo+(hi-lo)/2;
	 if(v[mid]<k+m&&mid!=poza&&mid!=pozb) ++nr,hi=mid-1;
	 else if(m+k>=v[mid]) lo=mid+1;
	 }
	   return -1;
}


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;i++)
	    for(j=i+1;j<x;j++)
	       {
		   a=v[i];b=v[j];poza=i;pozb=j;caut(a,b);
	       }

     printf("%d",nr);
   return 0;

}