Cod sursa(job #653233)

Utilizator an_drey_curentandreycurent an_drey_curent Data 27 decembrie 2011 17:21:53
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int N,v[640001],u[801],contor=0;
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}
int binary_search(int val)
{
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < N && u[i + step] <= val)
           i += step;
    return i;
}
int main()
{
	int i,j,ntri=0;
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&N);
	for(i=0;i<N;i++)
	{
		scanf("%d",&u[i]);
	}
	qsort(u,N,sizeof(int),compare);
	for(i=0;i<N;i++)
		for(j=i+1;j<N;j++)
		{
			int x=binary_search(u[i]+u[j]);
			ntri+=(x-j);
		}
	printf("%d",ntri);
	return 0;
}