Cod sursa(job #501342)

Utilizator popacamilpopa camil popacamil Data 14 noiembrie 2010 19:50:08
Problema Numarare triunghiuri Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.51 kb
#include<fstream>
using namespace std;
int 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;
					if (v[z]==(v[a]+v[b])) {break;}
				}
					else {m=z-1;}
			}	
			if(v[a]+v[b]>=v[z]){
				nrt+=(z-b);
			}
			else{nrt+=(z-b-1);}
		}
	}
	out<<nrt;
	return 0;
}