Cod sursa(job #693639)

Utilizator cristi103tiron cristian cristi103 Data 27 februarie 2012 14:50:32
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
using namespace std;
#include<fstream>
#include<iostream>
const int NMAX=805;
int v[NMAX],i,j,N,s=0;
void precalcul()
{
	for(i=1;i<N;++i)
		for(j=i+1;j<=N;j++)
			if(v[j]<v[i])
			{
				v[j]=v[i]+v[j];
				v[i]=v[j]-v[i];
				v[j]=v[j]-v[i];
			}
}

int cautare(int u, int p)
{
	int m;
	while(u<=p)
	{
		m=(u+p)/2;
		if(v[m]<=v[i]+v[j] && (v[m+1]>v[i]+v[j] || m==N))
			return m-j;
		if(v[m+1]<=v[i]+v[j])
			u=m+1;
		if(v[m]>v[i]+v[j])
			p=m-1;
	}
	return 0;
}

int main ()
{
	ifstream in("nrtri.in");
	ofstream out("nrtri.out");
	in>>N;
	for(i=1;i<=N;++i)
		in>>v[i];
	precalcul();
	for(i=1;i<N;++i)
		for(j=i+1;j<=N;++j)
			s+=cautare(1,N);
	out<<s<<'\n';
	in.close();out.close();
	return 0;
}