Cod sursa(job #1107912)

Utilizator BLz0rDospra Cristian BLz0r Data 14 februarie 2014 21:36:50
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<cstdio>
#include<algorithm>
#define maxn 805
using namespace std;

FILE *f=fopen("nrtri.in","r");
FILE *g=fopen("nrtri.out","w");
 
int v[805];
 
int bsearch(int x,int st,int dr){
	int m=(st+dr)/2;
	if (st<dr){
		if (v[m]<=x) bsearch(x,m+1,dr);
		else bsearch (x,st,m);
	}
    if (v[m]>x) m--;
    return m;
}
 
int main(){
	int n,k,x,s=0;
	fscanf (f,"%d",&n);

    for(int i=1;i<=n;++i) fscanf (f,"%d",&v[i]);
    sort(v+1,v+n+1);
	
    for(int i=1;i<=n-2;++i){
		for(int j=i+1;j<=n-1;++j){
			x=v[i]+v[j];
			k=bsearch (x,j+1,n);
			if(v[k]<=x) s+=(k-j);
		}                
	}
	
	fprintf (g,"%d",s);
  
    return 0;
}