Cod sursa(job #285440)

Utilizator vladbBogolin Vlad vladb Data 22 martie 2009 16:34:33
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>

using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n,a[801],p;

void quick(int x,int y)
{    	int i,j,p,aux;
	if(x<y)
	{	i=x-1;
		j=y+1;
		p=a[(x+y)/2];
		while(i<j)
		{	do i++; while(a[i]<p);
			do j--; while(a[j]>p);
			if(i<j) {  aux=a[i];
				   a[i]=a[j];
				   a[j]=aux;
				}
		}
		quick(x,i-1);
		quick(j+1,y);
	}
}

int cautabin(int i,int j)
{   int s=i,d=j,m;
    m=(s+d)/2;
    while(s<=d)
    {    if((a[m]<=a[i]+a[j]&&a[m+1]>a[i]+a[j])||(a[m]<=a[i]+a[j]&&m==n)) 
               return m;
          else if(a[m]<=a[i]+a[j]&&a[m+1]<=a[i]+a[j]) { s=m+1;
                                                        m=(s+d)/2;
                                                       }
                 else { d=m-1;
                        m=(s+d)/2;
                      }
    }
    return 0;
}

int main()
{   int i,j;
    fin>>n;
    for(i=1;i<=n;i++)
       fin>>a[i];
    quick(1,n);
    for(i=1;i<n-1;i++)
        for(j=1;j<n;j++)
        {   p+=cautabin(i,j);
        }    
    fout<<p-1;
    fin.close();
    fout.close();
    return 0;
}