Cod sursa(job #281865)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 16 martie 2009 08:33:56
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream.h>
#include<string.h>
#include<stdlib.h>
ifstream in("nrtri.in");
ofstream out("nrtri.out");
long x[1000],i,j,n,s,k;

int sort_function( const void *a, const void *b)
{
return( strcmp((char *)a,(char *)b) );
}
int bin(int a, int b, int st, int dr)
{
int mij=(st+dr)/2;
if(x[mij]<=a+b && x[mij]>=a-b && (!(x[mij+1]<=a+b && x[mij+1]>=a-b) || dr==mij) &&  (!(x[mij-1]<=a+b && x[mij-1]>=a-b) || st==mij))
	return mij;
if(st>=dr)
	return 0;
else
	{
	if(x[mij+1]<=a+b && x[mij+1]>=a-b)
		return bin(a,b, mij+1,dr);
	else
		return bin(a,b, st, mij-1);
	}
}

/*void sort(int k)
{
int t;
while(x[k]<x[k-1]&&n>1)
	{
	t=x[k];
	x[k]=x[k-1];
	x[k-1]=t;
	k--;
	}
} */

int main()
{
in>>n;
for(i=0; i<n; i++)
	{in>>x[i];}

qsort((void *)x, n, sizeof(x[0]), sort_function);

for(i=0; i<n; i++)
	for(j=i+1; j<n-1; j++)
		{
		k=bin(x[i],x[j],j+1,n-1);
		if(k)
			s+=(k-j);
		}
out<<s;
return 0;
}