Cod sursa(job #852001)

Utilizator dragos-giidragos ghinoiu dragos-gii Data 10 ianuarie 2013 18:45:38
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include<algorithm>
#include<fstream>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int v[801] , ca ;
int binar(int low , int high , int x){
	 int mid ;
	 while(low<=high){
		 mid=(low+high)/2;
		 if(v[mid]<=x)
			 low=mid+1;
		 else
			 high=mid-1;
	 }
	 return high;
}

int main(){
	 int N , i , j ;
	 fin>>N;
	 for(i=1 ; i<=N ; i++)
		 fin>>v[i];
	 sort(v+1,v+N+1);
	 for(i=1 ; i<=N-1 ; i++)
		 for(j=i+1 ; j<=N ; j++)
			 ca+=binar(i , N , v[i]+v[j])-j;
	 fout<<ca;
return 0;
}