Cod sursa(job #615891)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 11 octombrie 2011 09:42:12
Problema Numarare triunghiuri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<fstream>
#include<algorithm>
using namespace std;
short v[900],n;
long long k;
int caut_bin(int val,int s,int d) {
	int m=(s+d)/2;
	if(v[m]<=val&&v[m+1]>val)
		return m;
	else
	if(s==d) return 0;
	if(v[m]>=val) return caut_bin(val,s,m);
	else return caut_bin(val,m+1,d);
}
void vezi() {
	int i,j,r;
	for(i=0;i<n-2;i++)
		for(j=i+1;j<n-1;j++) {
			r=caut_bin(v[i]+v[j],j+1,n-1)-j;
			if(r>0) k+=r;
		}
}
void citire() {
	int i;
	ifstream in("nrtri.in");
	in>>n;
	for(i=0;i<n;i++)
		in>>v[i];
	in.close();
}
int main() {
	citire();
	sort(v,v+n);
	v[n]=v[n-1]+30001;
	vezi();
	ofstream out("nrtri.out");
	out<<k<<'\n';
	return 0;
}