Cod sursa(job #456922)

Utilizator siminescuPaval Cristi Onisim siminescu Data 17 mai 2010 12:12:01
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<fstream>
using namespace std;
#define nmax 802
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n,v[nmax],x1,x2;
void citire()
{
	f>>n;int i;
	for(i=1;i<=n;i++) f>>v[i];
}
void swap(int &i,int &j)
{
	int aux=i;i=j;j=aux;
}
void DownHeap( int from, int to )
{
    for( int son=2*from; son < to; from=son, son=2*from )
    {
        if( son < to-1 && v[son+1] > v[son] )
            ++son;
        if( v[from] >= v[son] )
            return;
        swap( v[from], v[son] );
    }
}
void HeapSort( int from, int to )
{
    int i;
    for( i=(to-from)/2; i > 0; --i )
        DownHeap( i, to );
    while( to > from )
    {
        swap( v[from], v[to-1] );
        --to;
        DownHeap( from, to );
    }
}
int search_left(int st)
{
	int dr=n,mij;
	while(st<dr)
	{
		mij=(st+dr)/2;
		if(v[mij]>=x2)dr=mij;
		else st=mij+1;
	}
	if(v[st]>=x2&&v[st]<=x1)return st-1;
	return 0;
}
int search_right(int st)
{
	int dr=n,mij;
	while(st<dr)
	{
		mij=(st+dr)/2+1;
		if(v[mij]<=x1)st=mij;
		else dr=mij-1;
	}
	if(v[dr]<=x1&&v[dr]>=x2)return dr;
	return 0;
}
int main()
{
	citire();HeapSort(1,n+1);
	int i,j,nr=0;
	for(i=1;i<n-1;i++)
		for(j=i+1;j<n;j++)
		{
			x1=v[i]+v[j];x2=v[j]-v[i];
			nr+=search_right(j+1)-search_left(j+1);
		}
	g<<nr<<'\n';
}