Cod sursa(job #789141)

Utilizator dogDaysAreOverAndreea Gheorghe dogDaysAreOver Data 17 septembrie 2012 00:51:16
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
/*
 * betisoare.cpp
 *
 *  Created on: Sep 15, 2012
 *      Author: ab
 */

#include <fstream>
#include <algorithm>
#include <vector>

#define input "nrtri.in"
#define outputFile "nrtri.out"
#define MAX 30000

using namespace std;

int n;
vector<int> lungimi;

bool possible(int a, int b, int c){

	return lungimi.at(c)<= lungimi.at(a) + lungimi.at(b) ;

}

int searchBete(int a, int b){
	int pos = -1;

	int start = b ;
	int end = n -1;

	while(start < end){
		int mid = (start + end + 1)/2;

		if(possible(a, b, mid))
			start = mid ;
		else
			end = mid - 1;
	}

	if(possible(a, b, start))
		pos = start;


	return pos;
}

int main(){
	int a, b,i, finalCount = 0;
	ifstream in(input);
	ofstream output;
	output.open(outputFile);

	in>>n;
	for( i =0; i<n; i++){
		in>>a;
		lungimi.push_back(a);
	}

	sort(lungimi.begin(), lungimi.end());

	for(a=0; a<n; a++ ){
		for(b=a+1; b<n; b++){
			int pos = searchBete(a, b);

			if(pos != -1)
				finalCount += pos - b  ;
		}
	}

	output << finalCount << endl;
	output.close();

}