Cod sursa(job #826113)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 30 noiembrie 2012 01:17:25
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream>
using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n, a[801], i, sum, pivot, st, dr, j, aux, sol, step, k;

void quicksort(int st, int dr){
		pivot = a[(st + dr)/2];
	i = st;
	j = dr;
	while(i <= j){
		while(pivot > a[i]) i++;
		while(pivot < a[j]) j--;
		if(i <= j){
			aux = a[i];
			a[i] = a[j];
			a[j] = aux;
		i++;
		j--;
		}
	}	
	if(st < j) quicksort(st, j);
	if(i < dr) quicksort(i, dr);
}


int main(){
	
	fin >> n;
	for(i=1; i<=n; ++i) fin >> a[i];
	quicksort(1, n);
	

	for(i=1; i<n; i++)
		for(j=i+1; j<n; j++) {			
			for(step=1; step<=n; step<<=1);
				for(k=0; step; step>>=1) if(k+step<=n && a[k+step]<=a[i]+a[j]) k+=step;
			if(a[i]+a[j]>=a[k] && a[k]+a[i]>=a[j] && a[k]+a[j]>=a[i]) sol+= k-j;
		}
	
	
	fout << sol;
	
	fin.close();
	fout.close();
	
	return 0;
}