Cod sursa(job #793975)

Utilizator petiVass Peter peti Data 4 octombrie 2012 21:32:23
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 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());

	int top=N;
	while(top>=2){
		int offset=1;
		top--;
		while(top>=offset){
			int s=search(v[top]-v[top-offset]);
			if(s>=top-offset) break;
			result+=top-offset-s;
			offset++;
		}
		
	}
	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;
}