Cod sursa(job #275960)

Utilizator mihnea_andreiMihnea Andrei mihnea_andrei Data 10 martie 2009 19:20:45
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream> 
#include<stdlib.h>
#define N 810

using namespace std; 

int n,v[N];

ifstream in ("nrtri.in"); 
ofstream out ("nrtri.out"); 

void citire () 
{ 
	in>>n; 
	for(int i=1;i<=n;i++) 
		in>>v[i];
}

int compar (const void *p, const void *q) 
{ 
	return ( *(int*)p - *(int*)q ); 
}

void sortare ()
{ 
	qsort(v+1,n,sizeof(v[0]),compar);
}

int cautbin (int x) 
{ 
	int mid,st,dr; 
	st=1; 
	dr=n; 
	while(st!=dr) 
	{
		mid=(st+dr)/2; 
		if(x<=v[mid]) 
			dr=mid; 
		else 
			st=mid+1;
	}
	if(x>=v[st]) 
		return st; 
	return st-1;
}

void calcul ()
{ 
	int s=0,p;
	for(int i=1;i<=n;i++)
	{		
		for(int j=i+1;j<=n;j++) 
		{ 
			p=cautbin(v[i]+v[j]);//p=ultima pozitie buna
			s=s+p-j;
		}
	}
	out<<s;
}

int main ()
{ 
	citire (); 
	sortare ();
	calcul (); 
	in.close (); 
	out.close (); 
	return 0; 
}