Cod sursa(job #88213)

Utilizator MirageRobert Sandu Mirage Data 30 septembrie 2007 21:11:08
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<stdio.h>
#include<stdlib.h>
int comp(const void *a, const void *b){
	int *aa=(int *)a, *bb=(int *)b;
	int x=*aa, y=*bb;
	return x-y;
}
int main () {
	int n,v[800],i,nr=0,j,p,u,m,k;
	FILE *in=fopen("nrtri.in","r"), *out=fopen("nrtri.out","w");
	fscanf(in,"%d",&n);
	for(i=0;i<n;i++)
		fscanf(in,"%d",&v[i]);
	qsort(v,n,sizeof(v[0]),comp);
	for(i=0;i<n-2;i++)
		for(j=i+1;j<n-1;j++){
			k=0;
			p=j+1;
			u=n-1;
			m=(p+u)/2;
			while(p<u){
				m=(p+u)/2;
				if(v[i]+v[j]>v[m])
					p=m+1;
				if(v[i]+v[j]<v[m])
					u=m;
				if(v[i]+v[j]==v[m]){
					p=u;
					nr+=m-j;
					k=1;
				}
			}
			if(v[i]+v[j]>=v[m]&&k==0)
				nr+=m-j;
		}
	fprintf(out,"%d\n",nr);
	fclose(in);
	fclose(out);
	return 0;
}