Cod sursa(job #1525145)

Utilizator backtrackIconaru Marian Catalin backtrack Data 14 noiembrie 2015 19:35:29
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
/*
int HoarePart(int l,int r,int *v){
	int i=l-1;
	int j=r+1;
	while(1){
		do{
			i++;
		}while(i<=j && v[i]<v[l]);
		do{
			j--;
		}while(j>=i && v[j]>v[l]);
		if(i<j)
			swap(v[i],v[j]);
		else
			return j;
	}
}

void quickSort(int l,int r,int *v){
	int pivot =HoarePart(l,r,v);
	if(l<pivot)
		quickSort(l,pivot,v);
	if(r>pivot+1)
		quickSort(pivot+1,r,v);
}
*/
int cautare_binara(int *v,int a,int b, int nr){
	if(a>b)
		return -1;
	int mij=(a+b)/2;
	if(v[mij]<=nr && b-a==0)
		return mij;
	if(v[mij+1]<=nr)
		return cautare_binara(v,mij+1,b,nr);
	if(v[mij]>nr)
		return cautare_binara(v,a,mij-1,nr);
	return mij;
}

int main(){
	int nr=0,k;
	ifstream f("nrtri.in");
	int n;
	f>>n;
	int *v=new int[n];
	for(int i=0;i<n;i++)
		f>>v[i];
	sort(v,v+n);
	
	for(int i=0;i<n-2;i++)
		for(int j=i+1;j<n-1;j++)
			if((k=cautare_binara(v,j+1,n-1,v[i]+v[j]))!=-1)
				nr+=k-j;
	ofstream g("nrtri.out");
	g<<nr;
	f.close();
	g.close();
	//system("pause");
	return 0;
}