Cod sursa(job #146033)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 1 martie 2008 08:14:05
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>
#include <stdlib.h>
int v[801],n;
int comp(const void *a, const void *b){
	int *aa=(int*)a,*bb=(int*)b;
	int aaa=*aa,bbb=*bb;
	return aaa-bbb;
}
int caut_x(int poz,int c){
	int m,i,st,dr;
	st=poz;
	dr=n;
	while(st<=dr){
		m=(st+dr)/2;
		if(v[m]>=c && (v[m-1]<c || m==poz)) 
			return m;
		else if(v[m]>=c) dr=m-1;
		else st=m+1;
	}
	return -1;
}
int caut_y(int poz,int c){
	int m,st,dr;
	st=poz;
	dr=n;
	while(st<=dr){
		m=(st+dr)/2;
		if(v[m]<=c && (v[m+1]>c || m==n))
			return m;
		else if(v[m]<=c) st=m+1;
		else dr=m-1;
	}
	return -1;
}
int main(){
	int i,j,x,y,sol=0;
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	v[0]=0;
	qsort(v,n+1,sizeof(v[0]),comp);
//	for(i=1;i<=n;i++)
//		printf("%d ",v[i]);
//	printf("\n");
	for(i=1;i<n-1;i++)
		for(j=i+1;j<n;j++){
			x=caut_x(j+1,v[j]-v[i]);
			y=caut_y(j+1,v[i]+v[j]);
//			printf("%d %d %d %d\n",i,j,x,y);
			if(x>0 && y>0) sol+=y-x+1;
		}
	printf("%d",sol);
	return 0;
}