Cod sursa(job #794090)

Utilizator petiVass Peter peti Data 5 octombrie 2012 16:36:21
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream ifs("nrtri.in");
ofstream ofs("nrtri.out");
int search(int x);
vector <int> v;
int N;
int result=0;

int main(){
	
	ifs>>N;
	v.resize(N);
	for(int i=0;i<N;i++)
		ifs>>v[i];
	
	sort(v.begin(),v.end());
	cout<<search(2);
	for(int i=N-1;i>=2;i--){
		for(int n=i-1;n>0;n--){
			int s=search(v[i]-v[n]);
			if(s>=n) break;
			else result+=n-s;
		}
	
	}
	
	ofs<<result;
	return 0;
}

//index of the first element in v that is >=x. Using some crippled binary search.
inline int search(int x){
	/* int  min=0,max=N;
	int pivot;	
	while(max>=min){
		pivot=(max+min)/2;
		if(x>v[pivot])
			min=pivot+1;
		else if(x<v[pivot])
			max=pivot-1;
		else
			return pivot;	
	}
	return pivot; */
	int i=0;
	
	while(v[i]<x)
		i++;
	return i;
	
	
}