Cod sursa(job #177061)

Utilizator AndreyPAndrei Poenaru AndreyP Data 12 aprilie 2008 10:22:27
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#include<stdlib.h>
#define N 810
int v[N],n;
char c[6*N];
int caut(int x)
{
	int p=0,u=n-1,m;
	while(p<u)
	{
		m=(p+u)/2;
		if(v[m]<x)
			p=m+1;
		else
			u=m;
	}
	while(v[p]>x)
		p--;
	while(v[p]==v[p+1])
		p++;
	return p;
}
int compar(const void *p,const void *q)
{
	int *pp=(int*)p,*qq=(int*)q;
	int u=*pp,w=*qq;
	if(u<w)
		return -1;
	if(u>w)
		return 1;
	return 0;
}
int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	int nr=0,i,r=0,j,aux,t;
	scanf("%d\n",&n);
	fgets(c,6*N,stdin);
	for(i=0; c[i]!='\0'; i++)
	{
		if((c[i]>='0')&&(c[i]<='9'))
			v[nr]=v[nr]*10+(c[i]-'0');
		else
			nr++;
	}
	qsort(v,n,sizeof(v[0]),compar);
	for(i=0; i<n; i++)
	{
		for(j=i+1; j<n; j++)
		{
			aux=v[i]+v[j];
			t=caut(aux);
			if(t>j)
				r+=t-j;
			//printf("%d %d %d\n",i+1,j+1,t+1);
		}
	}
	printf("%d\n",r);
	return 0;
}