Cod sursa(job #342741)

Utilizator bugyBogdan Vlad bugy Data 23 august 2009 12:41:18
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include<stdio.h>
using namespace std;
#define dim 100001 
int v[dim],y,x,n,tri=0; 
int caut_bin2 (int z,int j)   
{   
int inceput=j+1,sfarsit=n,mij,nr=n+1;   
    while (inceput<=sfarsit)   
    {mij=inceput+(sfarsit-inceput)/2;   
        if(v[mij]<=z)   
        { 
            nr=mij;   
            sfarsit=mij-1;   
        }   
        else    
            inceput=mij+1;   
    }   
    return nr;   
}
int caut_bin3 (int z,int j)   
{   
int inceput=j+1,sfarsit=n,mij,nr=n+1;   
    while (inceput<=sfarsit)   
    {mij=inceput+(sfarsit-inceput)/2;   
        if(v[mij]<=z)   
        { 
            nr=mij;   
            inceput=mij+1;   
        }   
        else    
            sfarsit=mij-1;   
    }   
	
    return nr;   
}


unsigned long quicksort(unsigned long inceput, unsigned long ultimul)      
{long long i,j,temp,aux,m=0;      





  i=inceput;      
  j=ultimul;      
  temp=v[(i+j)/2];      
 do     
   {while(v[i]<temp)      i=i+1;      
    while(v[j]>temp)      j=j-1;      
    if(i<j)      
     {aux=v[i]; v[i]=v[j]; v[j]=aux;m++;}      
    if(i<=j)      
     {j=j-1;      
      i=i+1;      
     }      
   }while(i<=j);      
   if(inceput<j)    quicksort(inceput,j);      
   if(i<ultimul)    quicksort(i,ultimul);      
   
}  



int main()
{
	int x1,x2,i,j,s=0;
FILE *f=fopen("nrtri.in","r"), *g=fopen("nrtri.out","w");   
  
      
    fscanf(f,"%d",&n);   
    for(i=1;i<=n;i++)   
        fscanf(f,"%d",&v[i]);   
   quicksort(1,n);   
    for(i=1;i<=n-2;i++)   
       for(j=i+1;j<=n-1;j++)   
	   {
	   s=v[i]+v[j];
	   x1=caut_bin2(s,j);
	   if(x1!=n+1)
		{ x2=caut_bin3(s,j);
		   if(x2!=n+1)
			  tri+=x2-x1+1;
		}
	   }
	
   
   
   
    fprintf(g,"%d\n",tri);   
	
	
fclose(f);	
fclose(g);
	
return 0;}