Cod sursa(job #473045)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 27 iulie 2010 20:00:11
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<fstream>
#include<algorithm>
 using namespace std;
    ifstream f("nrtri.in");
	ofstream g("nrtri.out");
	int n,a[801],i,j,mx,mx1,sol;
	
	int bs(int in,int sf,int find){
		int ret;
		while(in<=sf){
			int m=(in+sf)/2;
			if(a[m]<=find){//cauti mai sus
				in=m+1;
				ret=m;
			}
			else sf=m-1;
		}
		return ret;
	}
	
	int main(){
		f>>n;
		for(i=1;i<=n;++i) f>>a[i];
		sort(a+1,a+n+1);
		for(i=1;i<n;++i)
			for(j=i+1;j<=n;++j)
				if(i!=j){
					mx1=bs(1,n,a[i]+a[j]);//1,n,suma lor
					mx=max(i,j);
					sol+=(mx1-mx);
				}
		g<<sol<<'\n';
		g.close();
		return 0;
	}