Cod sursa(job #521379)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 12 ianuarie 2011 11:22:10
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f=fopen("nrtri.in","r");
FILE *g=fopen("nrtri.out","w");
int n,v[801];

int bin(int a,int b,int c,int d){
	int register p=d+1,u=n,m,nr=0;
	while(p<=u){
		m=p+(u-p)/2;
		if(a+b>=v[m]){
			p=m+1;
		}
		else
			u=m-1;
	}
	if(u>d)
		nr+=(u-d);
	return nr;
}

int main(void){
	int register i,j;
	
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++){
		fscanf(f,"%d",&v[i]);
	}
	sort(v+1,v+n+1);
	register int nr=0;
	for(i=1;i<n-1;i++){
		for(j=i+1;j<n;j++){
			nr+=bin(v[i],v[j],i,j);
		}
	}
	fprintf(g,"%d",nr);
	return 0;
}