Cod sursa(job #501348)

Utilizator popacamilpopa camil popacamil Data 14 noiembrie 2010 20:02:06
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.48 kb
#include<fstream>
using namespace std;
long long n,i,v[805],a,b,z,nrt,c,m;
int main(){
	ifstream in("nrtri.in"); ofstream out("nrtri.out");
	in>>n;
	for(i=1;i<=n;i++){
		in>>v[i];
	}
	sort(v+1,v+n+1);
    for(a=1; a<=n-2; a++){
		for(b=a+1; b<=n-1;b++){
			c=b;m=n;
			while (c<=m){
				z=(c+m)/2;
				if(v[z]<=(v[a]+v[b])){
					c=z+1;
				}
					else {m=z-1;}
			}	
			if(v[a]+v[b]>=v[z]){
				nrt+=(z-b);
			}
			else{nrt+=(z-b-1);}
		}
	}
	out<<nrt;
	return 0;
}