Cod sursa(job #57796)

Utilizator MirageRobert Sandu Mirage Data 3 mai 2007 00:28:54
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.49 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int main () {
	int n,v[800],i,nr=0,j,p,u,m;
	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]);
	sort(v,v+n);
	for(i=0;i<n;i++)
		for(j=i+1;j<n;j++){
			p=0;u=n-1;
			while(p<u){
				m=(p+u)/2;
				if((v[i]+v[j])<=v[m])
					u=m;
				else
					p=m+1;
			}
			nr+=p-j;
		}
	fprintf(out,"%d\n",nr/2);
	fclose(in);
	fclose(out);
	return 0;
}