Cod sursa(job #634101)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 15 noiembrie 2011 17:37:32
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 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;
	while(s<=d) {
		m=(s+d)/2;
		if(m==n-1||(v[m]<=val&&v[m+1]>val))
			return m;
		else
		if(v[m]>val) d=m-1;
		else s=m+1;
		}
	return -1;
}
void vezi() {
	int i,j,r;
	for(i=0;i<n-1;i++)
		for(j=i+1;j<n;j++) {
			r=caut_bin(v[i]+v[j],j,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;
}