Cod sursa(job #1524328)

Utilizator backtrackIconaru Marian Catalin backtrack Data 13 noiembrie 2015 21:58:52
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<iostream>
#include<fstream>

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)
		return mij;
	else if(v[mij]>nr)
		return cautare_binara(v,a,mij-1,nr);
}

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